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 |
人生第二次TARJAN,发帖,纪念哈!#include<stdio.h> #include<iostream> #include<vector> using namespace std; int ctc,id,n,m,top,st[101],ctd1[101],ctd2[101],dfn[101],low[101],ist[101],ict[101]; vector<int> gr[101]; vector<int> ct[101]; void tarjan(int i) {int j,k; dfn[i]=low[i]=id++; ist[i]=1; st[++top]=i; for(k=0;k<gr[i].size();k++) {j=gr[i][k]; if(dfn[j]==-1) {tarjan(j); low[i]=min(low[i],low[j]); } else if(ist[j]) low[i]=min(low[i],dfn[j]); } if(low[i]==dfn[i]) {ctc++; do {j=st[top--]; ist[j]=0; ict[j]=ctc; ct[ctc].push_back(j); }while(j!=i); } } int main() {freopen("poj1236.in","r",stdin); freopen("poj1236.out","w",stdout); int i,j,ans1=0,ans2=0,k; cin>>n; for(i=1;i<=n;i++) while(scanf("%d",&j)&&j!=0) gr[i].push_back(j); memset(dfn,-1,sizeof(dfn)); memset(low,-1,sizeof(low)); for(i=1;i<=n;i++) if(dfn[i]==-1) tarjan(i); for(i=1;i<=n;i++) for(k=0;k<gr[i].size();k++) {j=gr[i][k]; if(ict[i]!=ict[j]) {ctd1[ict[j]]++; ctd2[ict[i]]++; } } for(i=1;i<=ctc;i++){ans1+=!ctd1[i];ans2+=!ctd2[i];} cout<<ans1<<endl<<(ctc==1?0:max(ans1,ans2)); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator