uva 280 - Vertex-白红宇

uva 280 - Vertex

阅读量：5855 次

发布时间：2019-06-19

本文共 4123 字，大约阅读时间需要 13 分钟。

1 #include 
     
       2 #include 
      
        3 using namespace std; 4  5 #include 
       
         6 #define loop(i, n) for (int i = 0; i < n; i++) 7 #define loopfrom1(i, n) for (int i =1; i < n; i++) 8 #define pb(a) push_back(a) 9 #define SZ size()10 #define getint(n) scanf("%d", &n)11 12 #define MAXX 10513 #define looptill(i, n) for (int i = 0; i <= n; i++)14 15 vector
        
          Graph[MAXX];16 bool visited[MAXX];17 int inaccessible;18 19 void dfs(int u)20 {21     int len = Graph[u].SZ;22     int v;23     loop(i, len)24     {25         v = Graph[u][i];26         if( ! visited[v] )27         {28             visited[v] = true;29             inaccessible --;30             dfs(v);31         }32     }33 }34 35 int main()36 {37     int number_of_nodes, total_nodes;38     int node1, node2;39     while(true)40     {41         getint(total_nodes);42         if(total_nodes == 0) break;43         looptill(i, total_nodes)44         {45             Graph[i].clear();46         }47 48         while(true)49         {50             getint(node1);51             if(node1 == 0) break;52             while(true)53             {54                 getint (node2);55                 if(node2 == 0) break;56                 Graph[node1].pb(node2);57             }58         }59 60         getint(number_of_nodes);61         loop(t, number_of_nodes)62         {63             looptill(i, total_nodes)64             {65                 visited[i] = false;66             }67             68             getint(node1);69             inaccessible = total_nodes;70             dfs(node1);71 72             cout << inaccessible;73 74             for (int j = 1; j <= total_nodes; j++)75             {76                 if( ! visited[j] )77                 {78                     cout <<" "<

1 // @BEGIN_OF_SOURCE_CODE  2   3 #include 
     
        4 #include 
      
         5 #include 
       
          6 #include 
        
           7 #include 
         
            8 #include 
          
            9 #include 
            10 #include 
            
              11 #include 
             
               12 #define For(a) for ( i = 0; i < a; i++ ) 13 #define Rep(a, b) for ( i = a; i <= b; i++ ) 14 #define N 1000000 15 using namespace std; 16 17 enum related_color {gray, white, black}; 18 19 bool matrix [100 + 2] [100 + 2]; 20 bool related_vertics [100 + 2]; 21 related_color color [100 + 2]; 22 int number_of_vertics_n; 23 24 void reset_all (int n) 25 { 26 for ( int i = 0; i < n; i++ ) { 27 for ( int j = 0; j < n; j++ ) 28 matrix [i] [j] = false; 29 } 30 } 31 32 void dfs (int u) 33 { 34 color [u] = gray; 35 36 for ( int i = 0; i < number_of_vertics_n; i++ ) { 37 if ( matrix [u] [i] ) { 38 related_vertics [i] = true; 39 if ( color [i] == white ) { 40 related_vertics [i] = true; 41 dfs (i); 42 } 43 } 44 } 45 46 color [u] = black; 47 } 48 49 int main () 50 { 51 while ( scanf ("%d", &number_of_vertics_n) && number_of_vertics_n ) { 52 reset_all (number_of_vertics_n); 53 54 int starting_vertex; 55 56 while ( scanf ("%d", &starting_vertex) && starting_vertex ) { 57 int series_of_edges; 58 while ( scanf ("%d", &series_of_edges) && series_of_edges ) { 59 matrix [starting_vertex - 1] [series_of_edges - 1] = true; 60 } 61 } 62 63 int testCase; 64 scanf ("%d", &testCase); 65 66 while ( testCase-- ) { 67 int query; 68 scanf ("%d", &query); 69 70 for ( int i = 0; i < number_of_vertics_n; i++ ) { 71 related_vertics [i] = false; 72 color [i] = white; 73 } 74 75 dfs (query - 1); 76 77 vector 
              
                v; 78 79 for ( int i = 0; i < number_of_vertics_n; i++ ) { 80 if ( !related_vertics [i] ) 81 v.push_back (i + 1); 82 } 83 84 printf ("%d", v.size ()); 85 86 for ( unsigned int i = 0; i < v.size (); i++ ) 87 printf (" %d", v [i]); 88 89 printf ("\n"); 90 } 91 92 /* 93 for ( int i = 0; i < number_of_vertics_n; i++ ) { 94 for ( int j = 0; j < number_of_vertics_n; j++ ) 95 related_vertics [j] = false; 96 97 dfs (i); 98 99 for ( int j = 0; j < number_of_vertics_n; j++ ) {100 if ( related_vertics [j] )101 matrix [i] [j] = true;102 }103 }104 */105 }106 107 return 0;108 }109 110 // @END_OF_SOURCE_CODE