pku 2186
注意此題是單case，若想統(tǒng)計有幾個連通分量可以根據(jù)belong數(shù)組進行操作。
#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];//深搜時候，記錄節(jié)點是否被訪問過
int N,M;
int end_order[N1];//記錄深搜的時候，節(jié)點訪問結(jié)束順序
int index;
int first[N1]; //用于存儲圖，first[i]指向第一條起始節(jié)點為i的邊
int belong[N1];//belong[i]記錄節(jié)點i屬于哪個強連通分量
int cnt[N1]; //cnt[i]記錄節(jié)點i強連通分量中節(jié)點的數(shù)量
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;//記錄節(jié)點訪問結(jié)束順序
}
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;//記錄節(jié)點所屬的強連通分量
cnt[k]++;//強連通分量內(nèi)節(jié)點計數(shù)
}
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數(shù)組的構(gòu)建
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++){//統(tǒng)計無出邊的強連通分量的個數(shù)
if(!is_out[i]){
no_out++;
ans=cnt[i];
}
}
if(no_out==1)//輸出
printf("%d\n", ans);
else
printf("0\n");
return 0;
}