Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## ac

Posted by huzujun at 2013-03-18 21:26:04 on Problem 1236
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<vector>
using namespace std;
const int maxn=200;
vector<int> a[maxn];
int belong[maxn],low[maxn],dfn[maxn],sta[maxn];
int chu[maxn],ru[maxn];
bool insta[maxn];
int cnt=0,id=0,tp=0;

void dfs(int x)
{
low[x]=dfn[x]=++id;
sta[++tp]=x; insta[x]=true;
for (int k=0; k<a[x].size(); k++)
{
int y=a[x][k];
if (dfn[y]==0)
{
dfs(y);
if (low[x]>low[y]) low[x]=low[y];
}
else if (insta[y] && low[x]>dfn[y]) low[x]=dfn[y];
}
if (low[x]==dfn[x])
{
cnt++;
int i;
do
{
i=sta[tp--];
insta[i]=false;
belong[i]=cnt;
}while (i!=x);
}
}

int main()
{
int n;
scanf("%d", &n);
memset(dfn,0,sizeof(dfn));
memset(insta,false,sizeof(insta));
for (int i=1; i<=n; i++)
{
while (1)
{
int x;
scanf("%d", &x);
if (x==0) break;
a[i].push_back(x);
}
}

for (int i=1; i<=n; i++)
if (dfn[i]==0) dfs(i);
if(cnt==1) { printf("1\n0\n"); return 0;}
memset(chu,0,sizeof(chu));
memset(ru,0,sizeof(ru));
for (int i=1; i<=n; i++)
for (int j=0; j<a[i].size(); j++)
if (belong[i]!=belong[a[i][j]])
{
chu[belong[i]]++;
ru[belong[a[i][j]]]++;
}
int gr=0,gc=0;
for(int i=1; i<=cnt; i++)
{
if(chu[i]==0) gc++;
if(ru[i]==0) gr++;
}
int ans=0;
for (int i=1; i<=cnt; i++)
if (ru[i]==0) ans++;
printf("%d\n%d\n", ans, gc>gr?gc:gr);
return 0;
}

Followed by: