連結成分 Connected Components

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 }