백준 4803번: 트리

#include <iostream>
#include <queue>
#include <iterator>
#include <vector>
using namespace std;
int n, m,tree=0,key=0;
bool check[502];


void CycleCheck(vector<int> v[],int start) {
//cout << "error" << endl;
key = 0;
int i;
vector<int> ::iterator iter;
queue<int> q;
if (v[start].size() == 0) {
//cout << "start: " << start << endl;
tree++;
return;
}
q.push(start);
while (!q.empty()) {

int temp = q.front();
//cout << "temp: " <<temp<< endl;
q.pop();
if (check[temp]==true) {//cycle
key = -1;//cycle 표시 일단 다 순환해서 true 바꿔야
continue;
}
else { check[temp] = true; }
for (i = 0; i<v[temp].size(); i++) {
if (check[v[temp][i]] == true) {//cycle
/*cout << "cycle temp: " << temp << endl;
cout << "cycle v[temp][i]: " << v[temp][i] << endl;*/
key = -1;
continue;
}
else {
q.push(v[temp][i]);
//cout << "error2" << endl;
if (v[v[temp][i]].size() != 0) {
for (iter = v[v[temp][i]].begin(); iter != v[v[temp][i]].end(); iter++) {
//cout << "iter: " << *iter << endl;
if (*iter == temp) {
/*cout << "v[temp][i]: " << v[temp][i] << endl;
cout << "iter == temp: " << *iter << endl;*/
v[v[temp][i]].erase(iter);
break;
}

}
//cout << "error3" << endl;
}
}
}
}
if (key == 0)
tree++;
else if (key == -1)
return;
}

int main(void) {
int a=0,b=0,i, Case=0;
while (true) {
Case++;
tree = 0;
fill(check, check + 502, false);
scanf("%d %d", &n, &m);
if (n == 0 && m == 0)
break;
vector<int> * v = new vector<int>[n + 2];
for (i = 0; i < m; i++) {
scanf("%d %d", &a, &b);
v[a].push_back(b);
v[b].push_back(a);
}
for (i = 1; i < n + 1; i++) {
if(check[i]==false)
CycleCheck(v, i);
}
cout << "Case " << Case << ": ";
if (tree == 0)
cout << "No trees." << endl;
else if (tree == 1)
cout << "There is one tree." << endl;
else
cout << "A forest of " << tree << " trees." << endl;
delete[] v;
}
}

 

 

트리가 cycle인지 아닌지를 판명해야 했던 문제.

cycle인지 판명할 때, 시작 노드부터 시작해서 BFS 로 순환하며 check 한다. 

순환하며 queue에 들어간 A의 원소들이 이미 check[] true 라면, 그 노드는 cycle 인 것이다. 

이 때, 내가 queue에 새로 추가할 노드가 A->B 방향으로 B를 추가할 때, B가 queue에 들어가면 , B 역시 B->A 를 포함하므로, cycle 판명할 때 잘못 걸리게 됌. 그러므로 A->B 방향으로 B를 추가했다면, B->A 는 간선을 없에므로 cycle 판명을 가능케 한다.