poj3180 强连通

题意:给定一张 n 点 m 边的有向图,问有多少个强连通分量点数大于等于2 。

题意看懂基本就没有问题了。

 #include<stdio.h>
#include<string.h>
#include<stack>
#include<queue>
using namespace std; const int maxn=1e4+;
const int maxm=5e4+; int head[maxn],point[maxm],nxt[maxm],size;
int n,t,scccnt;
int stx[maxn],low[maxn],scc[maxn];
int num[maxn];
stack<int>S; void init(){
memset(head,-,sizeof(head));
size=;
memset(num,,sizeof(num));
} void add(int a,int b){
point[size]=b;
nxt[size]=head[a];
head[a]=size++;
} void dfs(int s){
stx[s]=low[s]=++t;
S.push(s);
for(int i=head[s];~i;i=nxt[i]){
int j=point[i];
if(!stx[j]){
dfs(j);
low[s]=min(low[s],low[j]);
}
else if(!scc[j]){
low[s]=min(low[s],stx[j]);
}
}
if(low[s]==stx[s]){
scccnt++;
while(){
int u=S.top();S.pop();
scc[u]=scccnt;
num[scccnt]++;
if(s==u)break;
}
}
} void setscc(){
memset(stx,,sizeof(stx));
memset(scc,,sizeof(scc));
t=scccnt=;
for(int i=;i<=n;++i)if(!stx[i])dfs(i);
} int main(){
int m;
scanf("%d%d",&n,&m);
init();
while(m--){
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
}
setscc();
int ans=;
for(int i=;i<=scccnt;++i)if(num[i]>)ans++;
printf("%d\n",ans);
return ;
}
上一篇:[LeetCode] Baseball Game 棒球游戏


下一篇:git submodule使用的笔记