At the end of the FJOI 2010 summer camp, many campers proposed to record the information of the whole summer camp into a CD-ROM for you to continue your study after you go back. The organizing committee thinks it's a good idea! However, the organizing committee did not have enough empty CD-ROMs for a while, so it could not guarantee that everyone could get the CD-ROM which recorded the information. What should we do? DYJ analyzed the geographical relationship of all battalion members and found that some battalion members are a city. In fact, they only need one, because when one person gets a CD, others can take something like a U-disk to copy it! ____________ They are willing to have some people copy information from him or others copy information from him, which is incompatible with the teamwork spirit advocated by our FJOI!!! Now suppose that there are a total of N battalions (2<=N<=200) with each battalion numbered from 1 to N. DYJ sent out a questionnaire to everyone, asking each battalion member to fill in who he would like to have copied information to him. Of course, if A is willing to copy the information to B and B is willing to copy the information to C, then once A gets the information, B and C will get the information. Now, please write a program to help DYJ figure out how many CD-ROMs the organizing committee needs to burn according to the collected questionnaires, so that all the campers can get the information of the summer camp when they return.

First is a number of N, then N lines, respectively, indicating that each battalion member is willing to copy the information they have obtained to the other battalion members. That is, line i+1 of the input data indicates that the first battalion member is willing to copy the data to the number of those battalions, ending with a zero. If a battalion member is unwilling to copy information to anyone, the corresponding line has only one line of 10, with a space separating several numbers in the line.

A positive integer representing the minimum number of discs to be burned.   

 5 

2 4 3 0 

4 5 0 

0 

0 

1 0  

1

2<=N<=200

Thought: Flyoed+KO Violence

One thing to note here is that nmap arrays may initially be written as nmap[j][i]=1, but in fact they are not. If nmap[j][i]=1, extreme data will go wrong, and I don't know why.

so nmap arrays can be theoretically removed.

Daddy's data.

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 using namespace std;
  5 const int maxn=0x7fffffff;
  6 int map[101][101];
  7 int nmap[101][101];
  8 int n;
  9 int vis[101];
 10 int pass[101];
 11 int now=1;
 12 int tot;
 13 void dfs(int p)
 14 {
 15     vis[p]=1;
 16     for(int i=1;i<=n;i++)
 17     {
 18         if(vis[i]==0&&map[p][i]==1)
 19         {
 20             dfs(i);
 21         }
 22     }
 23     pass[now]=p;
 24     now++;
 25 }
 26 void ndfs(int p)
 27 {
 28     vis[p]=0;
 29     for(int i=1;i<=n;i++)
 30     {
 31         if(vis[i]==1&&nmap[p][i]==1)
 32         {
 33             ndfs(i);
 34         }
 35     }
 36 }
 37 int main()
 38 {
 39     for(int i=1;i<=101;i++)
 40     for(int j=1;j<=101;j++)
 41     {
 42         map[i][j]=maxn;
 43         nmap[i][j]=maxn;
 44     }
 45     scanf("%d",&n);
 46     for(int i=1;i<=n;i++)
 47     {
 48         int j;
 49         while(scanf("%d",&j))
 50         {
 51             if(j==0)
 52             break;
 53             else
 54             {
 55                 map[i][j]=1;
 56                 nmap[i][j]=1;
 57             }
 58         }
 59     }
 60     for(int k=1;k<=n;k++)
 61     {
 62         for(int i=1;i<=n;i++)
 63         {
 64             for(int j=1;j<=n;j++)
 65             {
 66                 if(map[i][k]!=maxn&&map[k][j]!=maxn)
 67                 {
 68                     map[i][j]=map[i][j]||(map[i][k]+map[k][j]);
 69                     nmap[i][j]=nmap[i][j]||(nmap[i][k]+nmap[k][j]);
 70                 }
 71                 /*if(map[i][j]>map[i][k]+map[k][j])
 72                 {
 73                     map[i][j]=map[i][k]+map[k][j];
 74                 }
 75                 if(nmap[i][k]!=maxn&&nmap[k][j]!=maxn)
 76                 {
 77                     if(nmap[i][j]>nmap[i][k]+nmap[k][j])
 78                     {
 79                         nmap[i][j]=nmap[i][k]+nmap[k][j];
 80                     }
 81                 }*/
 82             }
 83         }
 84     }
 85     memset(vis,0,sizeof(vis));
 86     for(int i=1;i<=n;i++)
 87     {
 88         if(vis[i]==0)
 89         {
 90             dfs(i);
 91         }
 92     }
 93     for(int i=n;i>=1;i--)
 94     {
 95         if(vis[pass[i]]==1)
 96         {
 97             ndfs(pass[i]);
 98             tot++;
 99         }
100     }
101     printf("%d",tot);
102     return 0;
103 }