[ BOJ 백준 3977번 - 축구 전술 ] 해설 및 코드

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

 

목적

A구역에서 B구역으로 이동하게 하는 움직임이 주어질 때, 다른 모든 구역에 도달할 수 있는 시작 구역을 찾자.

 

접근법

1. 코사라주 알고리즘으로 찾은 첫번째 SCC가 정답의 후보이고, 이 SCC에서 다른 모든 정점으로 갈 수 있다면 정답이 된다.

 

2. dfs만 신나게 돌리자.

 

 

#include<bits/stdc++.h>
#define f(i,l,r) for(int i=l;i<r;++i)
using namespace std;
typedef vector<vector<int>> vvi;
typedef vector<int> vi;
 
const int MAXN=1e5;
bool vis[MAXN];
 
void dfs(int u, vvi &edge, vi &list){
    vis[u]=true;
    for(int &v:edge[u])if(!vis[v])dfs(v,edge,list);
    list.push_back(u);
}
 
int count(int u, vvi &edge){
    int cnt=1;
    vis[u]=true;
    for(int &v:edge[u])if(!vis[v])cnt+=count(v,edge);
    return cnt;
}
 
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int tc;cin>>tc;
    while(tc--){
        int n,m;cin>>n>>m;
        vvi edge(n),redge(n);
        while(m--){
            int a,b;cin>>a>>b;
            edge[a].push_back(b);
            redge[b].push_back(a);
        }
        
        vi order;
        memset(vis, false, n);
        f(i,0,n)if(!vis[i])dfs(i,edge,order);
        
        vi startScc;
        memset(vis, false, n);
        dfs(order.back(),redge,startScc);
        
        memset(vis, false, n);
        if(count(startScc[0],edge)==n){
            sort(startScc.begin(),startScc.end());
            for(int u:startScc)cout<<u<<'\n';
        }
        else cout<<"Confused\n";
        cout<<'\n';
    }
    return 0;
}
 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.