連結成分 Connected Components
2007.03.07 18:08 グラフ 探索

001 #define MAX 1000 002 int size; 003 int adjMatrix[MAX][MAX]; // graph structure 004 bool visited[MAX]; 005 int group[MAX]; 006 007 void visit( int currentNode, int id ){ 008 visited[currentNode] = true; 009 group[currentNode] = id; 010 011 for ( int nextNode = 0; nextNode < size; nextNode++ ){ 012 if ( !adjMatrix[currentNode][nextNode] ) continue; 013 if ( !visited[nextNode] ){ 014 visit( nextNode, id ); 015 } 016 } 017 } 018 019 void depthFirstSearch(){ 020 for ( int i = 0; i < size; i++ ) visited[ i ] = false; 021 int number = 1; 022 for ( int startNode = 0; startNode < size; startNode++ ){ 023 if ( !visited[startNode] ) visit( startNode, number++ ); 024 } 025 } 026 027 void inputGraph(){ 028 cin >> size; 029 030 for ( int i = 0; i < size; i++ ){ 031 for ( int j = 0; j < size; j++ ){ 032 adjMatrix[i][j] = 0; 033 } 034 } 035 036 int source, target; 037 // input based on adjMatrix 038 for ( int source = 0; source < size; source++ ){ 039 for ( int target = 0; target < size; target++ ){ 040 cin >> adjMatrix[source][target]; 041 } 042 } 043 } 044 045 int main(){ 046 inputGraph(); 047 depthFirstSearch(); 048 049 for ( int i = 0; i < size; i++ ){ 050 cout << i << " " << group[i] << endl; 051 } 052 return 0; 053 }
スポンサーサイト
| コメント(0) | トラックバック(0) | ↑ページトップ |