1
ACM 算法资料集锦 2009 年 12 月 10 日星期四
for(i=0;i<n;i++){
if(id[i]==0)
s.push(i);
}
if(s.size()!=1) OK=false;
int count=0;
while(!s.empty()){
int v=s.top(); s.pop(); count++;
order.push_back(v);
list<int>::iterator k;
for(k=g[v].begin();k!=g[v].end();k++){
id[*k]--;
if(id[*k]==0) s.push(*k);
if(s.size()>1) OK=false;
}
}
if(order.size() < n) OK=false; //矛盾发生,会导致这种情况,小心
if(count < n) incon=true;
copy(&t[0],&t[n],&id[0]);
}
DFS 强连通分支
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define M 20005
vector<int> g[M],gt[M];
bool used[M];
int ft[M],sort_v[M],tim;
bool comp(const int &u,const int &v){
return ft[u]>ft[v];
}
inline int findp(int set[],int n){
int n2=n;
while(set[n]!=0) n=set[n];
if(n2!=n) set[n2]=n;
return n;
}
inline bool uni(int set[],int a,int b){
int ac=0,a2=a,b2=b,bc=0,t;
while(set[a]!=0) {a=set[a];ac++;}
while(a2!=a) {t=set[a2]; set[a2]=a; a2=t;};
while(set[b]!=0) {b=set[b];bc++;}
while(b2!=b) {t=set[b2]; set[b2]=b; b2=t;};
if(a==b) return false;
if(ac<bc) set[a]=b;
else set[b]=a;
return true;
}
void dfs(vector<int> g[M],int u){
if(used[u]) return;
tim++;
used[u]=true;
int i;
for(i=0;i<g[u].size();i++){
dfs(g,g[u][i]);
}
tim++;
ft[u]=tim;
return;
}
void dfs2(vector<int> g[],int u,int r,int set[]){
if(used[u]) return;
uni(set,u,r);
used[u]=true;
int i;
for(i=0;i<g[u].size();i++){
dfs2(g,g[u][i],u,set);
}
return;
}
void scc(int n,vector<int> g[M],int set[]){
int i,j;
tim=0;
memset(used,0,sizeof(used));
memset(set,0,sizeof(set));
for(i=1;i<=n;i++) sort_v[i]=i;
for(i=1;i<=n;i++) if(!used[i]) dfs(g,i); //compute finishing times
sort(&sort_v[1],&sort_v[n+1],comp); //decreasing f[u] order
memset(used,0,sizeof(used));
for(i=1;i<=n;i++) for(j=0;j<g[i].size();j++) gt[g[i]
[j]].push_back(i); //compute gt
for(i=1;i<=n;i++) if(!used[sort_v[i]])
dfs2(gt,sort_v[i],sort_v[i],set); //make the scc
}
int main(){
int i,j,n,m,u,v,set[M];
cin >> n >> m;
for(i=0;i<m;i++){
scanf("%d%d",&u,&v);
评论0
最新资源