459-Graph Connectivity

<br /> /* <br /> "Graph Connectivity"<br /> Level:5.0<br /> Date:2007/2/11<br /> 技巧:<br /> 先建立adjacency matrix, <br /> 再用DFS traversal找sub graph的數目.<br /> 題目的input data可能是夾雜空白的,所以需要對input data filter掉多餘的空白,<br /> read.erase(remove(read.begin(), read.end(), ' '), read.end());<br /> 上面這招很好用,多謝強哥教我....orz..<br /> */<br /> <br /> #include <iostream><br /> #include <string><br /> #include <algorithm><br /> <br /> using namespace std;<br /> int ans, size;<br /> bool visited[26], table[26][26]; <br /> <br /> void DFS(int node){<br /> visited[node] = true;<br /> for(int i=0;i < size;++i){ if(table[node][i] == true && visited[i] == false) DFS(i); } } int main(){ int turn, n1, n2; string c; string read; cin>>turn;<br /> <br /> while(turn--){<br /> ans = 0;<br /> cin>>c;<br /> cin.ignore(); //清除stream裡的多餘字完('\n') <br /> size = c[0] - 'A'+1;<br /> <br /> for(int i=0; i < 26; ++i) for(int j=0; j < 26; ++j) table[i][j] = false; while(1){ //建立adjcent matrix. getline(cin, read); read.erase(remove(read.begin(), read.end(), ' '), read.end()); //filter掉多餘空白. if( read.empty() == true) break; n1 = read[0] - 'A'; n2 = read[1] - 'A'; table[n1][n2] = true; table[n2][n1] = true; } for(int i=0; i < size; ++i){ if(visited[i] == false){ DFS(i); ++ans; } } cout<< ans << endl; if(turn != 0) cout << endl; for(int i=0;i < size;++i) visited[i]= false; } return 0; }