ZOMBIEROAD

AOJ ZOMBIEROAD

SOL)

좀비로드가 아닌 정점을 방문해야 한다.
따라서 set에 방문을 해야하는 정점을 기록.

BFS 탐색을 통해 방문을 해야하는 정점이 나오는 경우 parent배열을 통해 역추적을 한다.
역추적 과정에서 map에 기록한 zombieroad가 있으면 ans++후 삭제
역추적 과정에서 이미 확인한 간선인 경우 더이상 조상루트들을 확인할 필요가 없기 때문에 break

[-] Collapse

#include<cstring>
#include<cstdio>
#include<vector>
#include<map>
#include<set>
#include<queue>
using namespace std;
bool visited[20001];
vector<vector<int> >adj;
set<int> visit;
map<pair<int,int>, int> zRoad, check;
int parent[20001];
int BFS(){
    int ans = 0;
    queue<int> mq;
    mq.push(*visit.begin());
    visited[*visit.begin()] = true;
    while (!mq.empty()){
        int sink = mq.front();
        mq.pop();
        for (int i = 0; i < adj[sink].size(); i++){
            int dd = adj[sink][i];
            if (!visited[adj[sink][i]]){
                mq.push(adj[sink][i]);
                parent[adj[sink][i]] = sink;
                visited[adj[sink][i]] = true;
            }
            else continue;
            set<int>::iterator it = visit.find(adj[sink][i]);
            if (it != visit.end()){
                int v = *it;
                while (true){
                    if (check.count(make_pair(v, parent[v])) > 0 || check.count(make_pair(parent[v], v)) > 0 || parent[v] == -1) break;
                    if (zRoad.count(make_pair(parent[v], v)) > 0){
                        ans++;
                        zRoad.erase(make_pair(parent[v], v));
                        zRoad.erase(make_pair(v, parent[v]));
                        check[make_pair(parent[v], v)]++;
                        check[make_pair(v, parent[v])]++;
                    }
                    v = parent[v];
                }
            }
        }
    }
    return ans;
}
int main(){
    int t; scanf("%d", &t);
    while (t--){
        memset(visited, false, sizeof(visited));
        memset(parent, -1, sizeof(parent));
        zRoad.clear(); check.clear();
        visit.clear();
        int n; scanf("%d", &n);
        adj = vector<vector<int> >(n);
        for (int i = 0; i < n-1; i++){
            int u, v, val; scanf("%d%d%d", &u, &v, &val);
            adj[u].push_back(v); adj[v].push_back(u);
            if (val == 0) visit.insert(u);
            if (val == 1) zRoad[make_pair(u, v)]++, zRoad[make_pair(v, u)]++;
        }
        printf("%d\n", BFS());
    }
}