| ||||||||||
| 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