ACOJ-12176-校园网.md

title: ACOJ 12176 校园网 categories: 割点割边 tags: [代码,编程] date: 2019-02-16 16:34:00

• 摘要:代码，好像错了一个点吧

/*
代码90%的成分都是有机物，只需要一点火星就可以引燃，引燃代码，拯救地球。
省实验楚才楼交委提醒您：代码千万行，正确第一行，敲键不规范，考完两行泪。
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACA
*/
#include <bits/stdc++.h>
#include <cstdio>

using namespace std;
int dfn[10010],low[10010],vis[10010],s[10010],color[10010],du[10010],cnt[10010],rudu[10010],rudutmp;
int n,m,top,sum,deep,tmp,ans;
vector<int> g[10010];

void tarjan(int u)
{
    dfn[u] = low[u] = ++deep;
    vis[u] = 1;
    s[++top] = u;
    int sz = g[u].size();
    for(int i=0; i<sz; i++)
    {
        int v=g[u][i];
        if(!dfn[v])
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else
        {
            if(vis[v])
            {
                low[u]=min(low[u],low[v]);
            }
        }
    }
    if(dfn[u] == low[u])
    {
        color[u] = ++sum;
        vis[u] = 0;
        while(s[top]!=u)
        {
            color[s[top]] = sum;
            vis[s[top--]] = 0;
        }
        top--;
    }
}

int main()
{
    cin>>n;
    int to;
    for(int i = 1; i<=n; i++)
    {
        scanf("%d",&to);
        while(to != 0){
            //cout<<i<<'-'<<to<<'-'<<i<<endl;
            g[i].push_back(to);
            //cout<<g[i][0];
            scanf("%d",&to);
        }
    }
    for(int i = 1; i<=n; i++)
    {
        if(!dfn[i])
            tarjan(i);
    }
    for(int i = 1; i<=n; i++)
    {
        int sz = g[i].size();
        for(int j = 0; j<sz; j++)
        {
            int v = g[i][j];
            if(color[v]!=color[i])
            {
                du[color[i]]++;
                rudu[color[v]]++;
            }

        }
        cnt[color[i]]++;
    }
    for(int i = 1; i<=sum; i++)
    {
        if(du[i] == 0)
        {
            tmp++;
            ans = cnt[i];

        }
        if(rudu[i] == 0){
            rudutmp++;
        }
    }
    /*
    if(tmp == 0)
    {
        cout<<0<<endl;

    }
    else if(tmp>1)
    {
        cout<<0<<endl;
    }
    else
        cout<<ans<<endl;
        */
    cout<<rudutmp<<'\n'<<max(tmp,rudutmp);

    //tmp 出度为0的点

    return 0;
}