1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 | #include<cstdio> #include<algorithm> #include<cstring> #include<queue> #include<vector> using namespace std; vector<int> arr[1001]; queue<int> q; bool check[1001]; void bfs(int start) { check[start]=true; q.push(start); while(!q.empty()) { int node=q.front(); q.pop(); for(int i=0; i<arr[node].size(); i++) { int next=arr[node][i]; if(check[next]==false) { check[next]=true; q.push(next); } } } } int main(void) { int t,n,a,cnt; scanf("%d", &t); while(t--) { cnt=0; scanf("%d", &n); for(int i=1; i<=n; i++) { scanf("%d", &a); arr[i].push_back(a); } for(int i=1; i<=n; i++) { if(check[i]==false) { bfs(i); //printf("%d ", i); cnt++; } } printf("%d\n", cnt); memset(check,false,sizeof(check)); while(!q.empty()) q.pop(); for(int i=0; i<=n; i++) arr[i].clear(); } return 0; } | cs |
'백준 2 > 그래프' 카테고리의 다른 글
| [백준 7569] 토마토 (C++/Python) (0) | 2020.12.08 |
|---|---|
| [백준 7576] 토마토 (C++/Python) (0) | 2020.12.08 |
| [백준 1707] 이분 그래프 (C++/Java) (0) | 2020.12.08 |
| [백준 11724] 연결 요소의 개수 (C++/Java) (0) | 2020.12.08 |
| [백준 1260] DFS와 BFS (C++/Python) (0) | 2020.12.08 |