强连通分量 B3609

AC Code

# include<iostream>
using namespace std;

const int N=1e4+5,M=1e5+5;

struct edge{
	int v,next;
}e[M];

int n,m,x,y;
int head[N],cnt=0;
int dfn[N],low[N],num=0;
int top=0,st[N];//模拟栈 
int co[N],col=0;//co: 结点i所在强连通分量的编号  
bool vis[N];

void add(int x,int y){
	e[++cnt].next=head[x];
	head[x]=cnt;
	e[cnt].v=y;
}

void tarjan(int u){
	dfn[u]=low[u]=++num;
	st[++top]=u;//u入栈 
	for(int i=head[u];i;i=e[i].next){
		int v=e[i].v;
		if(!dfn[v]){
			tarjan(v);//继续向下找 
			low[u]=min(low[u],low[v]);
		}
		//如果v还在栈内，即v不属于任何强连通分量 
		else if(!co[v])
			low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u]){
		co[u]=++col;
		//将st[top]退栈，其为强连通分量内的一个节点 
		while(st[top]!=u) co[st[top--]]=col;
		--top;//将u退栈 
	}
}

int main(){
	cin>>n>>m;
	for(int i=0;i<m;++i){
		cin>>x>>y;
		if(x!=y) add(x,y);
	}
	for(int i=1;i<=n;++i)
		if(!dfn[i]) tarjan(i);
	cout<<col<<endl;
	for(int i=1;i<=n;++i){
		if(!vis[i]){
			for(int j=i;j<=n;++j)
				if(co[j]==co[i]){
					cout<<j<<" ";
					vis[j]=1;
				}
			cout<<endl;
		}
	}
}

原始模板

# include<iostream>
using namespace std;

const int N=1e4+5,M=5e4+5;

struct edge{
	int v,next;
}e[M];

int n,m,x,y;
int head[N],cnt=0;
int dfn[N],low[N],num=0;
int top=0,st[N];
int co[N],col=0;

void add(int x,int y){
	e[++cnt].next=head[x];
	head[x]=cnt;
	e[cnt].v=y;
}

void tarjan(int u){
	dfn[u]=low[u]=++num;
	st[++top]=u;
	for(int i=head[u];i;i=e[i].next){
		int v=e[i].v;
		if(!dfn[v]){
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(!co[v])
			low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u]){
		co[u]=++col;
		while(st[top]!=u) co[st[top--]]=col;
		--top;
	}
}

int main(){
	cin>>n>>m;
	for(int i=0;i<m;++i){
		cin>>x>>y;
		if(x!=y) add(x,y);
	}
	for(int i=1;i<=n;++i)
		if(!dfn[i]) tarjan(i);
	return 0;
}

缩点 P3387

# include<iostream>
# include<vector>
# include<algorithm>
# include<queue>
using namespace std;
# define ll long long

const int N=1e4+5,M=1e5+5;

struct edge{
	int v,next;
}e[M];

int n,m,x,y;
int head[N],cnt=0;
int dfn[N],low[N],num=0;
int top=0,st[N];
int co[N],col=0;

ll a[N],s[N],dp[N],ans;
int p[N],d[N],k=0;
queue<int> q;
vector<int> e1[N];

void add(int x,int y){
	e[++cnt].next=head[x];
	head[x]=cnt;
	e[cnt].v=y;
}

void tarjan(int u){
	dfn[u]=low[u]=++num;
	st[++top]=u;
	for(int i=head[u];i;i=e[i].next){
		int v=e[i].v;
		if(!dfn[v]){
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(!co[v])
			low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u]){
		co[u]=++col;
		while(st[top]!=u) co[st[top--]]=col;
		--top;
	}
}

void toposort(){
	for(int i=1;i<=col;++i){
		dp[i]=s[i];
		if(!d[i]) q.push(i);
	}
	while(!q.empty()){
		int u=q.front();
		q.pop();
		p[++k]=u;
		for(int i=0;i<e1[u].size();++i){
			int v=e1[u][i];
			d[v]--;
			if(!d[v]) q.push(v);
		}
	}
}

int main(){
	cin>>n>>m;
	for(int i=1;i<=n;++i) cin>>a[i];
	for(int i=1;i<=m;++i){
		cin>>x>>y;
		if(x!=y) add(x,y);
	}
	for(int i=1;i<=n;++i)
		if(!dfn[i]) tarjan(i);
	for(int i=1;i<=n;++i){
		s[co[i]]+=a[i];
		for(int j=head[i];j;j=e[j].next){
			int u=co[i],v=co[e[j].v];
			if(u!=v){
				e1[u].push_back(v);
				d[v]++;
			}
		}
	}
	toposort();
	for(int i=1;i<=k;++i){
		int u=p[i];
		ans=max(ans,dp[u]);
		for(int j=0;j<e1[u].size();++j){
			int v=e1[u][j];
			dp[v]=max(dp[v],dp[u]+s[v]);
		}
	}
	cout<<ans;
	return 0;
}

割点 P3388

# include<iostream>
using namespace std;

const int N=2e4+5,M=1e5+5;

struct edge{
	int v,next;
}e[2*M];

int head[N],dfn[N],low[N];
int cnt=0,num=0,n,m,x,y,sum=0,root;
bool cut[N];

void add(int x,int y){
	e[++cnt].next=head[x];
	head[x]=cnt;
	e[cnt].v=y;
}

void tarjan(int u){
	dfn[u]=low[u]=++num;
	int s=0;
	for(int i=head[u];i;i=e[i].next){
		int v=e[i].v;
		if(!dfn[v]){
			s++;
			tarjan(v); 
			low[u]=min(low[u],low[v]);
			//两个条件
			if(!cut[u]&&u!=root&&dfn[u]<=low[v]){
				++sum;
				cut[u]=1;
			}
		}
		//因为是无向图 
		else low[u]=min(low[u],dfn[v]);
	}
	if(!cut[u]&&u==root&&s>1){
		++sum;
		cut[u]=1;
	}
}

int main(){
	cin>>n>>m;
	for(int i=0;i<m;++i){
		cin>>x>>y;
		add(x,y);
		add(y,x);
	}
	for(int i=1;i<=n;++i)
		if(!dfn[i]){
			root=i;
			tarjan(i);
		}
	cout<<sum<<endl;
	for(int i=1;i<=n;++i)
		if(cut[i]) cout<<i<<" ";
}