[SWEA] 7988 내전 경기

 

문제가 좀 복잡해 보이는데 잘 읽어보면 dfs를 이용해서 풀 수 있다

먼저 입력으로 들어오는 이름들은 map을 통해 숫자롤 매겨주자

 

그리고 시너지가 발생하는 조합을 통해 그래프를 만들어준다

 

그래프를 다 만들었다면

이제 문제는 나와 연결된 정점과 다른색으로 색칠하며 dfs를 돌릴 수 있냐!

이걸로 바뀌게 된다

 

나와 연결된 정점들에 나와 다른색을 주면서 dfs를 돌아보자

만약 같은색이 있다면 false! 다 돌수 있다면 true 다

 

하나라도 false가 나오면 No가 답이다

 

 

소스코드

#include <bits/stdc++.h>
using namespace std;
#define ll long long
 
int t,k;
 
bool check[222];
int color[222];
bool solve(vector<vector<int>>& Graph,int pos){
    check[pos]=true;
    for(int i=0;i<Graph[pos].size();i++){
        int next = Graph[pos][i];
        if(color[next]==color[pos]) return false;
        if(!check[next]) {
            color[next]=!color[pos];
            if(!solve(Graph,next)) return false;
        }
    }
    return true;
}
int main(){
    scanf(" %d",&t);
    for(int tc=1;tc<=t;tc++){
        memset(check,0,sizeof(check));
        memset(color,-1,sizeof(color));
        scanf(" %d",&k);
        int pos=0;
        map<string,int> mp;
        vector<pair<int,int>> vt;
        for(int i=0;i<k;i++){
            string a,b; cin>>a>>b;
            if(!mp.count(a)) mp[a]=pos++;
            if(!mp.count(b)) mp[b]=pos++;
            vt.push_back({mp[a],mp[b]});
        }
        vector<vector<int>> Graph(pos);
        for(int i=0;i<k;i++){
            int x=vt[i].first;
            int y=vt[i].second;
            Graph[x].push_back(y);
            Graph[y].push_back(x);
        }
        
        bool ans=true;
        for(int i=0;i<pos;i++){
            if(!check[i]){
                color[i]=0;
                ans&=solve(Graph,i);
            }
        }
        printf("#%d %s\n",tc,(ans) ? "Yes" : "No"); 
    }
}