Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  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:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator