Code[VS] 1332 题解【Kosaraju】【Tarjan】

Code[VS] 1332 上白泽慧音题解

题目描述 Description

在幻想乡，上白泽慧音是以知识渊博闻名的老师。春雪异变导致人间之里的很多道路都被大雪堵塞，使有的学生不能顺利地到达慧音所在的村庄。因此慧音决定换一个能够聚集最多人数的村庄作为新的教学地点。人间之里由N个村庄（编号为1..N）和M条道路组成，道路分为两种一种为单向通行的，一种为双向通行的，分别用1和2来标记。如果存在由村庄A到达村庄B的通路，那么我们认为可以从村庄A到达村庄B，记为(A,B)。当(A,B)和(B,A)同时满足时，我们认为A,B是绝对连通的，记为<A,B>。绝对连通区域是指一个村庄的集合，在这个集合中任意两个村庄X,Y都满足<X,Y>。现在你的任务是，找出最大的绝对连通区域，并将这个绝对连通区域的村庄按编号依次输出。若存在两个最大的，输出字典序最小的，比如当存在1,3,4和2,5,6这两个最大连通区域时，输出的是1,3,4。

输入描述 Input Description

第1行：两个正整数N,M

第2..M+1行：每行三个正整数a,b,t, t = 1表示存在从村庄a到b的单向道路，t = 2表示村庄a,b之间存在双向通行的道路。保证每条道路只出现一次。

输出描述 Output Description

第1行： 1个整数，表示最大的绝对连通区域包含的村庄个数。

第2行：若干个整数，依次输出最大的绝对连通区域所包含的村庄编号。

样例输入 Sample Input

5 5

1 2 1

1 3 2

2 4 2

5 1 2

3 5 1

样例输出 Sample Output

1 3 5

数据范围及提示 Data Size & Hint

对于60%的数据：N <= 200且M <= 10,000

对于100%的数据：N <= 5,000且M <= 50,000

—————————————————————————分割线—————————————————————————

分析

这道题是明显的求强连通分量裸题,需要对强连通分量进行简单的染色，再统计即可。

可以使用Tarjan或Kosaraju算法

代码如下：

 1 /*
 2    Tarjan algorithm 
 3    author : SHHHS
 4    2016-09-13 19:01:12 
 5 */
 6 #include "cstdio"
 7 #include "iostream"
 8 
 9 using namespace std ;
10 const int maxN  = 200010 ;
11 const int INF = 2147483647 ;
12 
13 struct Tarjan {int to , next ;}e[ maxN ] ;
14 int head[ maxN ] , color[ maxN ] , stack[ maxN ] ,dfn[ maxN ] , low[ maxN ] , s[ maxN ];
15 bool vis [ maxN ] ;
16 
17 int cnt = 0 , ans = -INF , dfs_num = 0 , col_num = 0 , top  ;
18 
19 int gmin ( int x , int y ) {
20          return x < y  ? x : y ;
21 }
22 
23 void Add_Edge ( int x , int y ) {
24          e[ ++cnt ].to = y ;
25          e[ cnt ].next = head[ x ] ;
26          head[ x ] = cnt ;
27          return ;
28 }
29 
30 void Tarjan ( int x ) {
31          dfn[ x ] = ++dfs_num ;
32          low[ x ] = dfs_num ;
33          vis [ x ] = true ;
34          stack [ ++top ] = x ;
35          for ( int i=head[ x ] ; i!=0 ; i=e[i].next ){
36                   int temp = e[ i ].to ;
37                   if ( !dfn[ temp ] ){
38                            Tarjan ( temp ) ;
39                            low[ x ] = gmin ( low[ x ] , low[ temp ] ) ;
40                  }
41                  else if ( vis[ temp ])low[ x ] = gmin ( low[ x ] , dfn[ temp ] ) ;
42          }
43          if ( dfn[ x ]==low[ x ] ) {
44                   vis[ x ] = false ;
45                   color[ x ] = ++col_num ;
46                   s[ col_num ] ++ ;
47                   while ( stack[ top ] != x ) {
48                            s[ col_num ] ++ ;
49                            color [stack[ top ]] = col_num ;
50                            vis [ stack[ top-- ] ] = false ;
51                  }
52                  top -- ;
53          }
54 }
55 int main ( ) {
56          int N , M , target ;
57          
58          std::ios::sync_with_stdio ( 0 ) ; 
59          
60          cin >> N >> M ;
61          for ( int i=1 ; i<=M ; ++i ) {
62                   int x , y , _ ;
63                   cin >> x >> y >> _ ;
64                   Add_Edge ( x , y ) ;
65                   if ( _-1 ) Add_Edge ( y , x ) ;
66          }
67          for ( int i=1 ; i<=N ; ++i ) {
68                   if ( !dfn[ i ] )  
69                           Tarjan ( i ) ; 
70          }
71          for ( int i=1 ; i<=N ; ++i ) {
72                   if( s[color[ i ]]>ans ) {
73                            ans = s[color[i]] , target = i ;
74                  }
75          }
76          cout << ans << endl ;
77          for ( int i=1 ; i<=N ; ++i ) {
78                   if ( color[ i ]==color[ target ]) {
79                            cout << i << ' ' ;
80                  }
81          }
82          return 0 ;
83 }

/*
     Kosaraju algorithm 
     author : SHHHS
     2016-09-18 00:32:28
*/

#include "cstdio"
#include "iostream"
#include "algorithm"

using namespace std ;

const int maxN = 100100 , maxM = 500100;

struct Kosaraju { int to , next ; } ;

Kosaraju E[ 2 ][ maxM ] ;
bool vis[ maxN ];
int head[ 2 ][ maxN ] , cnt[ 2 ] , ord[maxN] , size[maxN] ,color[ maxN ];

int tot , dfs_num  , col_num , N , M  ;

void Add_Edge( int x , int y , int _ ){//建图 
         E[ _ ][ ++cnt[ _ ] ].to = y ;
         E[ _ ][ cnt[ _ ] ].next = head[ _ ][ x ] ;
         head[ _ ][ x ] = cnt[ _ ] ;
}

void DFS_1 ( int x , int _ ){
         dfs_num ++ ;//发现时间 
         vis[ x ] = true ;
         for ( int i = head[_][x] ; i ; i = E[_][i].next ) {
                 int temp = E[_][i].to;
                 if(vis[temp] == false) DFS_1 ( temp , _) ;
         }
         ord[(N<<1) + 1 - (++dfs_num) ] = x ;//完成时间加入栈 
}

void DFS_2 ( int x , int _ ){
         // 强连通分量的大小 
         vis[ x ] = false ;
         color[ x ] = col_num ;//染色 
         size[ color[ x ] ]++ ;
         for ( int i=head[ _ ][ x ] ; i ; i = E[ _ ][ i ].next ) {
                 int temp = E[_][i].to;
                 if(vis[temp] == true) DFS_2(temp , _);
         } 
}

int main ( ){
         scanf("%d %d" , &N , &M );
         for ( int i=1 ; i<=M ; ++i ){
                 int _x , _y , _ ;
                 scanf("%d %d %d" , &_x , &_y , &_ ) ;
                 Add_Edge( _x , _y , 0 ) ;//原图的邻接表 
                 Add_Edge( _y , _x , 1 ) ;//逆图的邻接表 
                 if ( _-1 ){
                           Add_Edge( _y , _x , 0 ) ;
                           Add_Edge( _x , _y , 1 ) ;
                 }
         }
         for ( int i=1 ; i<=N ; ++i ) 
                 if ( vis[ i ]==false ) 
                          DFS_1 ( i , 0 ) ;//原图的DFS 

         for ( int i = 1 ; i<=(N<<1) ; ++i ) {
                 if( ord[ i ]!=0 && vis[ ord[ i ] ] ){
                          tot ++ ; //强连通分量的个数 
                          col_num ++ ;//染色的颜色 
                          DFS_2 ( ord[ i ] , 1 ) ;
                 }
         }
         int ans = -2147483647 , target ;
         for ( int i=1 ; i<=N ; ++i ) {
                  if( size[color[ i ]]>ans ) {
                           ans = size[color[i]] , target = i ;
                 }
         }
         printf ( "%d
" , ans ) ;
         for ( int i=1 ; i<=N ; ++i ) {
                  if ( color[ i ]==color[ target ]) {
                           printf ( "%d " , i ) ;
                 }
         }
         return 0;
}

2016-09-14

(完)

Code[VS] 1332 题解 【Kosaraju】【Tarjan】

Code[VS] 1332 上白泽慧音题解

Code[VS] 1332 题解【Kosaraju】【Tarjan】