백준 9372번 - 상근이의 여행

https://www.acmicpc.net/problem/9372

이전에 풀었던 네트워크 연결과 유사한 문제이다.

차이점은 가중치가 없기 때문에 정렬할 필요없이 입력한 순서대로 집합을 만들어나가면 된다.

parent값이 같다는 것은 이미 연결되어 있다는 것이기 때문에 패스하면 된다.

#include <iostream>
#include <vector>
using namespace std;
 
struct str{
    int u,v,w;
    str(int u,int v):u(u),v(v){};
};
 
vector<int> parent;
 
int find(int p){
    if(parent[p]!=p){
        p=find(parent[p]);
    }
    
    return p;
}
int main(){
    
    int T;
    cin>>T;
    
    int N,M;
    int u,v;
    for(int testCase=0;testCase<T;testCase++){
        scanf("%d %d",&N,&M);
        
        vector<str> vec;
        parent=vector<int> (N+1,0);
        int ans=0;
        
        for(int i=0;i<M;i++){
            scanf("%d %d",&u,&v);
            vec.push_back(str(u,v));
        }
        
        for(int i=1;i<=N;i++)
            parent[i]=i;
        
        for(int i=0;i<vec.size();i++){
            int p1=find(vec[i].u);
            int p2=find(vec[i].v);
            
            if(p1!=p2){
                parent[p1]=p2;
                ans++;
            }
        }
        
        cout<<ans<<endl;
    }
    
    return 0;
}