题解：P7251 [JSOI2014] 强连通图

强连通分量模板题。

首先 tarjan 求出原图中所有的强连通分量。对于第一问，因为每个强连通分量中的点两两可达，所以答案即为最大的强连通分量大小。

对于第二问。将每个强连通分量缩成一个点后，记入度为零的个数为

in

，出度为零的点的个数为

out

。如果

in<out

，对每个入度为零的点再连条边到出度为零的即可。反之亦然。所以答案为

\max(in,out)

。

注意特判原图只有一个强连通分量时，第二问不用多连任何边，所以答案为零。

CPP

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5+5;
int n,m; 
int low[N],dfn[N],stk[N],ins[N],siz[N],scc[N],idx,top,id,in[N],out[N];
vector<int> e[N];

void tarjan(int x){
	dfn[x]=low[x]=++idx,stk[++top]=x,ins[x]=1;
	for(int i=0;i<e[x].size();i++){
		int y=e[x][i];
		if(!dfn[y]){
			tarjan(y);
			low[x]=min(low[x],low[y]);
		}else if(ins[y])
			low[x]=min(low[x],dfn[y]);
	}
	if(dfn[x]==low[x]){
		int y; id++;
		do{
			y=stk[top--];
			ins[y]=0,siz[id]++;
			scc[y]=id;
		}while(x!=y);
	}
}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
    	int u,v; cin>>u>>v;
    	e[u].push_back(v);
	}
	for(int i=1;i<=n;i++)
		if(!dfn[i]) tarjan(i);
	for(int x=1;x<=n;x++){
		for(int i=0;i<e[x].size();i++){
			int y=e[x][i];
			if(scc[x]!=scc[y]){
				in[scc[y]]++,out[scc[x]]++;
			}
		}
	}
	if(id==1){
		cout<<siz[1]<<endl<<0;
		return 0;
	}
	int c=0,c1=0,c2=0;
	for(int i=1;i<=id;i++){
		c=max(c,siz[i]);
		if(!in[i]) c1++;
		if(!out[i]) c2++;
	}
	cout<<c<<endl<<max(c1,c2);
	return 0;
}

题解：P7251 [JSOI2014] 强连通图

文章操作

相关推荐

评论

题解：P7251 [JSOI2014] 强连通图