pku 2186
注意此题是单case，若想统计有几个连通分量可以根据belong数组进行操作。
#include<iostream>
#incldue<string.h>
#include<stdlib.h>
#include<stdio.h>
#define N1 50005
using namespace std;
struct Edge
{
int a, b;
}edges[N1];
bool visited[N1];//深搜时候，记录节点是否被访问过
int N,M;
int end_order[N1];//记录深搜的时候，节点访问结束顺序
int index;
int first[N1]; //用于存储图，first[i]指向第一条起始节点为i的边
int belong[N1];//belong[i]记录节点i属于哪个强连通分量
int cnt[N1]; //cnt[i]记录节点i强连通分量中节点的数量
bool is_out[N1]; //is_out[i]记录第i个强连通分量是否有出边
int cmp1(const void *a, const void *b)
{
return ((Edge*)a)->a-((Edge*)b)->a;
}
int cmp2(const void *a, const void *b)
{
return ((Edge*)a)->b-((Edge*)b)->b;
}
void dfs1(int source)
{
if(visited[source]) return ;
visited[source]=true;
for(int i=first[source]; i<first[source+1]; i++)
dfs1(edges[i].b);
end_order[index++]=source;//记录节点访问结束顺序
}
void dfs2(int source ,int k)
{
if(visited[source]) return ;
visited[source]=true;
for(int i=first[source]; i<first[source+1]; i++)
dfs2(edges[i].a, k);
belong[source]=k;//记录节点所属的强连通分量
cnt[k]++;//强连通分量内节点计数
}
int main()
{
int ans;
scanf("%d %d", &N, &M);
for(int i=0; i<M; i++){
scanf("%d %d", &edges[i].a, &edges[i].b);
edges[i].a--; edges[i].b--;
}
edges[M].a=edges[M].b=-1; //简化下面first数组的构建
qsort(edges, M, sizeof(edges[0]), cmp1);
int last_source=0;
first[last_source]=0;
int k=0;
while(last_source<N){
if(edges[k].a==last_source) k++;
else first[++last_source]=k;
}
memset(visited, 0, sizeof(visited));
index=0;
for(int i=0; i<N; i++)
dfs1(i);
qsort(edges, M , sizeof(edges[0]), cmp2);
last_source=0;
first[last_source]=0;
k=0;
while(last_source<N){
if(edges[k].b==last_source) k++;
else first[++last_source]=k;
}
memset(visited, 0, sizeof(visited));
memset(cnt, 0, sizeof(cnt));
k=0;
for(int i=index-1; i>=0; i--){
if(visited[end_order[i]]) continue;
dfs2(end_order[i], k); //第二次搜索
k++;
}
for(int i=0; i<M; i++){//记录哪些强连通分量有出边
if(belong[edges[i].a]!=belong[edges[i].b])
is_out[belong[edges[i].a]]=true;
}
int no_out=0;
for(int i=0; i<k; i++){//统计无出边的强连通分量的个数
if(!is_out[i]){
no_out++;
ans=cnt[i];
}
}
if(no_out==1)//输出
printf("%d\n", ans);
else
printf("0\n");
return 0;
}