[BOJ/Platinum 5] 백준 10292 Man in the Middle(C++)

문제 링크

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

10292번: Man in the Middle

 

문제

Nowadays, social networks are one of most active research topic. A social network represents friendships between people. We say that two people are direct friends if they accept each other as friends. But friendship is an amazing thing. It is possible that a person information shared to her/his direct friends gets shared to her/his friends of friends, and friends of friends of friends, and so on. 

We say that two people can reach each other if they are either direct friends, friends of friends, friends of friends of friends, and so on. 

Given a social network for which every pair of people can reach each other, we define Man in the Middle as a person who, if leaving the social network, breaks the condition that every pair of people can reach each other. It’s possible to have more than one Man in the Middle in a social network. Help us find if the given social network has any Man in the Middle! 

입력

On the first line there is a single integer T <= 15, number of test cases. Then T test cases follow. 

• Each test starts, on the first line, with two integers N <= 30,000 and M <= 300,000, number of people in a social network and number of friendships. 
• For the next M lines, each line contains 2 integers A and B, such that 1<=A<=N, 1<=B<=N, and A and B are distinct; this line shows that that A and B are direct friend. 

출력

The output should be T lines, each line representing one test case. For each line, output “YES” if the given social network has Man in the Middle, and “NO” otherwise. 

예제 입력 1

2
3 2
1 2
1 3
4 4
1 2
1 3
2 4
3 4

예제 출력 1

YES
NO

알고리즘 분류

• 그래프 탐색

풀이

각 테스트 케이스마다 주어진 그래프에서 단절점을 찾고, 단절점이 있다면 YES, 단절점이 없으면 NO를 출력한다.

그래프에서 어떤 정점이 단절점인 경우는 다음과 같다.

1. 정점이 Root일 때

  - 자식 정점이 2개 이상이라면 단절점이다.

2. 정점이 Root가 아닐 때

  - 정점보다 방문 순서가 뒤인 자식 정점들이 정점을 거치지 않고 정점보다 방문 순서가 앞인 정점들에 도달할 수 있다면 해당 정점은 단절점이 아니며, 도달할 수 없다면 해당 정점은 단절점이 된다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 30001
#define LL long long
#define INF 1e9

using namespace std;
int T, N, M;
vector<int> Edge[MAX];
int visited[MAX];
bool isCutNode[MAX];
int answer;

void Init() {
	answer = 0;
	for (int i = 0; i < MAX; i++) {
		Edge[i].clear();
		visited[i] = 0;
		isCutNode[i] = false;
	}
}

int DFS(int Parent, int Here, int Order, bool isRoot) {
	visited[Here] = Order;
	int res = visited[Here];
	int Child = 0;

	for (int i = 0; i < Edge[Here].size(); i++) {
		int Next = Edge[Here][i];
		if (Parent == Next) {
			continue;
		}

		if (visited[Next] > 0) {
			res = min(res, visited[Next]);
			continue;
		}

		Child++;
		int Next_Order = DFS(Here, Next, Order + 1, false);
		if (!isRoot && (visited[Here] <= Next_Order)) {
			isCutNode[Here] = true;
		}
		res = min(res, Next_Order);
	}

	if (isRoot && (Child >= 2)) {
		isCutNode[Here] = true;
	}

	return res;
}

void Settings() {
	for (int i = 1; i <= N; i++) {
		sort(Edge[i].begin(), Edge[i].end());
	}
	for (int i = 1; i <= N; i++) {
		if (visited[i] == 0) {
			DFS(0, i, 1, true);
		}
	}
}

void Find_Answer() {
	for (int i = 1; i <= N; i++) {
		if (isCutNode[i]) {
			answer++;
		}
	}
	if (answer == 0) {
		cout << "NO\n";
	}
	else {
		cout << "YES\n";
	}
}

void Input() {
	cin >> T;
	while (T--) {
		Init();
		cin >> N >> M;
		for (int i = 0; i < M; i++) {
			int A, B;
			cin >> A >> B;
			Edge[A].push_back(B);
			Edge[B].push_back(A);
		}
		Settings();
		Find_Answer();
	};
}

int main() {
	FASTIO
	Input();

	return 0;
}