[백준문제풀이] 3977 축구전술

 

풀이일시 : 2020-08-29

​

 

문제 :

World Soccer Championship이 다가오고 있다! 천재적인 전술을 창조하는 플랜 아티스트 감독 도현이는 자신의 팀이 승리하도록 만반의 준비를 가하고 있다. 도현이의 전략은 경기장을 여러 개의 구역으로 나누고, 어떤 선수가 A구역에서 B구역으로 이동하게 하는 움직임을 (A, B)로 표현한다. 모든 도현이의 팀 선수들이 이 움직임만을 따라서 이동한다면 승리하리라고 도현이는 확신한다.

도현이는 선수들에게 자신의 전술을 말해주며, 다른 모든 구역에 도달할 수 있는 시작 구역을 찾은 뒤 지시한 움직임만을 따라가라고 했다. 그러나 도현이는 한 가지 간과한 것이 있었는데 그건 선수들이 자신만큼 똑똑하지 않다는 것이다. 선수들은 그러한 시작 구역을 찾는 것이 어려웠다. 이제 당신이 적절한 시작 구역을 찾아줘야 한다.

​

 

입력:

첫 번째 줄에 테스트 케이스의 개수가 주어지며, 이는 11보다 작거나 같은 정수이다.

그 다음 줄부터 여러 개의 테스트 케이스가 주어지는데, 각 테스트 케이스마다 첫 번째 줄에 구역의 수 N, 지시한 움직임의 수 M이 주어지며 1 ≤ N, M ≤ 100,000 이다. 그 다음 M개의 줄에 걸쳐서 움직임 (A, B)가 주어지며, A, B는 0 ≤ A, B < N인 정수이다.

각 테스트 케이스는 하나의 빈 줄로 구분된다.

ex)

1

4 4

0 1

1 2

2 0

2 3

​

 

출력:

각 테스트 케이스마다 가능한 모든 시작 구역을 오름차순으로 한 줄에 하나씩 출력한다. 만약 그러한 시작 구역이 없으면, "Confused"를 출력한다.

각 테스트 케이스의 끝에는 하나의 빈 줄을 출력한다.

ex)

0

1

2

​

 

풀이 :

모든노드로 갈수있는 노드를 찾는 문제!

하나의 SCC에서 출발하여 모든 그래프를 방문할 수 있을때에 한해 출발 SCC의 모든 원소를 출력하는 문제이다.

출발 SCC를 찾으려면 진입차수가 0인 SCC를 찾으면된다.

진입차수가 0인 노드가 하나면 노드들의 번호를 출력해주면되고

진입차수가 0인 SCC가 여러개거나 존재하지 않는경우 Confused이다.

 

dbstndi6316.tistory.com/57

[기본문제풀이] 강한결합요소

#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
#define MAX 100001

using namespace std;

stack<int> s;
int n, m;
int id, d[MAX];
bool finished[MAX];
vector<int> a[MAX];
vector<vector<int>> SCC;
vector<int> result; //추가
int group[MAX];
bool inDegree[MAX];

//항상 처음 방문하는 노드만 실행된다. N번실행
int dfs(int x) {
	d[x] = ++id;
	s.push(x);
	int parent = d[x];
	for (int i = 0; i < a[x].size(); i++) {
		int y = a[x][i];
		if (d[y] == 0)
			parent = min(parent, dfs(y));
		else if (!finished[y])
			parent = min(parent, d[y]);
	}
	//부모노드가 자기 자신일 경우 SCC를 형성한다.
	if (parent == d[x]) {
		vector<int> scc;
		while (1) {
			int t = s.top();
			s.pop();
			scc.push_back(t);
			group[t] = SCC.size() + 1; //group을 이용하여 특정한 SCC에 대한 진입차수를 구하도록 만듦
			finished[t] = true;
			if (t == x)
				break;
		}
		SCC.push_back(scc);
	}
	//자신의 부모 값을 반환한다.
	return parent;
}

int main() {
	int t;
	scanf_s("%d", &t);
	while (t--) {
        //테스트케이스가 여러개일 수 있기때문에 클리어해주는 과정
		SCC.clear();
		fill(d, d + MAX, 0); //memset으로 대체가능 #include<cstring>
		fill(finished, finished + MAX, 0);
		fill(inDegree, inDegree + MAX, false);
		result.clear(); 

		scanf_s("%d %d", & n, &m);
		for (int i = 1; i <= n; i++) {
			a[i].clear();
		}

		for (int i = 0; i < m; i++) {
			int x, y;
			scanf_s("%d %d", &x, &y);
			a[x + 1].push_back(y + 1); //각 정점이 1부터 시작하도록 만들어야되기때문에 +1
		}

		for (int i = 1; i <= n; i++) {
			if (d[i] == 0) //모든 정점에 대해서 dfs
				dfs(i);
		}

		for (int i = 1; i <= n; i++) { //진입차수를 구해준다.
			//모든 정점을 다 확인하면서 다른 그룹으로 넘어가는 구간에 대해서
			//진입차수를 확인한다.
			for (int j = 0; j < a[i].size(); j++) {
				int y = a[i][j];
				if (group[i] != group[y]) { //같은 group에 속해있지 않으면
					inDegree[group[y]] = true; 
				}
			}
		}
		int count = 0;

		//정답 도출부분
		for (int i = 0; i < SCC.size(); i++) { //강한결합요소 다 확인하도록
			if (!inDegree[i + 1]) { //특정한 SCC에 진입차수가 없는경우
				count++; //센다
				for (int j = 0; j < SCC[i].size(); j++) { //그때에 한해서 해당원소를 다 담아준다.
					result.push_back(SCC[i][j] - 1); //result에 담아즌다
				}
			}
		}
		sort(result.begin(), result.end()); //오름차순으로
		if (count != 1) {
			printf("Confused\n\n");
		}
		else {
			for (int i = 0; i < result.size(); i++) {
				printf("%d\n", result[i]);
			}
			printf("\n");
		}
	}
	return 0;
}