記事タイトルPOJ 1236:Network of Schools(強聯通成分＋縮点)

Network of Schools
A number of school are connected to a computternetwork.Agreements have been developed among school:each school mantains a list of school to which it distributes softwarethen A does not necessar appar in the list of school＿B You are to write a program that computtes the minimal number of school receive a copy of the new Software in the ftware the ftware the ftware the dischone the corelstre.ウェウェウェトトトトトエンドストストストライトライトライトライトライトライトライトライトライトライトライトライトライトライトライトライトパネルパネルパネルパネルパネル、thisisissofftware school、thisisisisisisisisisisisisisgoaaattwork.To achieve thisgoaaaaaaaaaaaaaaaaaaatttthethethethe liststststrererererererererererereeeeeeeeeeeeeemmmmmmmmmmmmmmmmbebebes s s.eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeソフトドリンクト、it will reach all other school(Subtask B).One extens means introdcing one new member into the list of receivers of one school.Input The first line containteger N:the number of schone the-2The schools arare e e dentifed by the first N positive integers.Each of the next N ininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininsts.es.es.es.Eacaaaaaaaaaaae.Eacaaaaaaaaaaaaaaaainininininininininininput.The first line shoundcontain one positive integer:the solution of subtask A.The second line Shound contain the solution of subtask B.Sample Input 5 2 4 4 0 0 1 0 Sample Output 1 2
N(2＜N＜100)各学校の間に一方向のネットワークがあり、各学校はソフトウェアを入手した後、一方向ネットワークを通じて周辺の学校に転送することができます.1:最初に少なくともいくつかの学校にソフトウェアを配布する必要があります.ネットワーク内のすべての学校が最終的にソフトウェアを入手することができます.2,少なくともいくつかの伝送路を追加して、いずれかの学校にソフトウェアを配布した後、何回かの転送を経て、ネットワーク内のすべての学校は最終的にソフトウェアを得ることができます.
問題1については、つまり図の中に向かっていくつかの点を選ぶ必要があります.これらの点から全部の点に達することができます.問題2については、図の中にもういくつかの向辺があり、任意の頂点から出発して、他の頂点に達することができます.まず強い連結成分を求めて縮小して、図を再構築します.この時は方向図があります.その後、ANs 1で保存して、0の数を記録します.ans 2は度が0の数を保存して、問題1に対して、ans 1です.問題2については、max(ans 1,ans 2)コードです.

#include
#include
#include
#include
#include
#include
#include
#include 
#include
using namespace std;
const int inf = 0x3f3f3f3f;
typedef pair<int,int> pii;

const int maxn = 105;

int mp[105][105];

vector<int>G[maxn];
int belong[maxn];//           
int dfn[maxn],low[maxn];
int ins[maxn],block,id;
int st[maxn],tp;
int sz[maxn];   //        
int n; 
int rudu[maxn],chudu[maxn];//              

void init(){
    id=tp=block=0;
    memset (low,0,sizeof (low));
    memset (dfn,0,sizeof (dfn));
    memset (sz,0,sizeof (sz));
    memset (rudu,0,sizeof (rudu));
    memset (chudu,0,sizeof (chudu));
    memset (mp,0,sizeof (mp));
}

void tarjan(int u){
    dfn[u]=low[u]=++id;
    ins[u]=1;//       
    st[++tp]=u;//   
    for (int i=0;iint v=G[u][i];
        if (!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if (ins[v])low[u]=min(low[u],dfn[v]);
    } 
    if (low[u]==dfn[u]){
        block++;//       
        int v;
        do{
            v=st[tp--];
            ins[v]=0;
            belong[v]=block;
            sz[block]++;
        }while (u!=v);
    }
}

int main ()
{   
    while (scanf ("%d",&n)!=EOF){
        init();
        for (int i=0;i<=n;i++)G[i].clear();//   
        int tmp;
        for (int i=1;i<=n;i++){
            while (1){
                scanf ("%d",&tmp);
                if (tmp==0)break;
                mp[i][tmp]=1;//       
                G[i].push_back(tmp);//   
            }
        }
        for (int i=1;i<=n;i++){//      
            if (!dfn[i]){
                tarjan(i);
            }
        }
        if (block==1){//                 
            printf ("1
");
            printf ("0
");
            continue;
        }
        for (int i=1;i<=n;i++){
            for (int j=1;j<=n;j++){
                if (mp[i][j]==1){
                    if (belong[i]!=belong[j]){//                  
                        chudu[belong[i]]++;
                        rudu[belong[j]]++;
                    }
                }
            }
        }
        int ans1=0;
        int ans2=0;
        //printf ("block=%d
",block);
        for (int i=1;i<=block;i++){
            if (rudu[i]==0)ans1++;
            if (chudu[i]==0)ans2++;
        }
        printf ("%d
",ans1);
        printf ("%d
",max(ans1,ans2));
    }
    return 0;
}