Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
终于A了 贴代码留个痕迹,用list可能会快些#include<iostream> #include<list> #include<vector> using namespace std; const int MAX=10005; list<int>adj[MAX], adj_op[MAX]; bool visit[MAX]={0},out[MAX]; int sblg[MAX],n,m; vector<int> finish; void dfs1(int i) { if(visit[i])return ; visit[i]=true; for(int k=0; k<adj[i].size(); k++) if(!visit[adj[i][k]])dfs1(adj[i][k]); finish.push_back(i); } void dfs2(int i, int c) { if(visit[i])return ; visit[i]=true; sblg[i]=c; for(int k=0; k<adj_op[i].size(); k++) if(!visit[adj_op[i][k]])dfs2(adj_op[i][k],c); } int main() { while(cin>>n>>m) { memset(visit,0,sizeof visit); memset(out,0,sizeof out); memset(sblg,0,sizeof sblg); for(int i=1; i<=n; i++){ adj[i].clear(); adj_op[i].clear(); } int u,v; for(int i=1; i<=m; i++) { cin>>u>>v; adj[u].push_back(v); adj_op[v].push_back(u); } for(int i=1; i<=n; i++) if(!visit[i])dfs1(i); memset(visit,0,sizeof visit); int cnt=0; for(int i=finish.size()-1; i>=0; i--) { if(!visit[finish[i]]) { cnt++; dfs2(finish[i],cnt); } } for(int i=1; i<=n; i++) { for(int j=0; j<adj[i].size(); j++) { if(sblg[i]!=sblg[adj[i][j]])out[sblg[i]]=true; } } int count=0,index=0,num=0; for(int i=1; i<=cnt; i++) if(out[i]==0){ count++;index=i; } //for(int i=1; i<=n; i++) // cout<<sblg[i]<<endl; if(count==1) { for(int i=1; i<=n; i++) if(sblg[i]==index)num++; cout<<num<<endl; } else cout<<0<<endl; } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator