앳코더90 - 021 - Come Back in One Piece（★5）

https://atcoder.jp/contests/typical90/tasks/typical90_u

021 - Come Back in One Piece（★5）

 

N개의 정점과 M개의 간선을 가진 유향그래프가 있을 때 간선 i는 정점 Ai에서 정점 Bi로 향한다. 다음 조건을 만족하는 2개의 정점 (x,y)의 쌍 이 몇개 인지 구하라

- 정점 x에서 정점 y로 가는 경로와 정점 y에서 정점 x로 가는 경로가 모두 존재한다.

 

문제를 읽어 보고 나서 아이디어가 바로 떠올랐다. 정점 a에서 b로 b에서 a로 간다는 것은 사이클을 이루고 있는가? 와 같은 의미 아닌가? 싶어서 유향 그래프 안에서 사이클을 찾는 알고리즘 scc를 이용하는 문제다 싶었다.

 

https://b1ackhand.tistory.com/307

Atcoder ACL

ACL을 공부해 봤으니 ACL을 이용하여 더 간단하게 코드를 짜게 되었다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <unordered_set>
#include <numeric>
#include <random>
#include <iostream>
#include <unordered_map>
#include <atcoder/all>

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define range(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back

using namespace std;
using namespace atcoder;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef vector<int> vi;
typedef vector<long long> vll;

const int INF = 2000000000;
const double pi = 3.14159265358979;
const int MOD = 100000;

void yesno(bool a)
{
	if (a)
		cout << "YES\n";
	else
		cout << "NO\n";
}

int N, M;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> N >> M;

	scc_graph g(N + 1);

	rep(i, M)
	{
		int a, b;
		cin >> a >> b;
		g.add_edge(a, b);
	}

	auto scc = g.scc();

	ll ans = 0;

	for (auto i : scc)
	{
		if (i.size() != 1)
			ans += i.size();
	}

	cout << ans;

	return 0;
}

 

하지만 아쉽게도 일부만 맞고 나머지는 다 틀렸다. 일부 맞았다는것은 방향성이 틀리지 않았다는 것인데, i.size() != 1 이 부분이 문제 인 것 같았다. 해당 부분은 정점이 사이클을 이루지 않고 떨어져 있으면 크기가 1인 scc를 이루기 때문에 제외 시킨건데 이 부분을 다시 생각해봤을 때, 크기가 3인 scc a, b, c가 이루는 서로에가 닷는 정점의 쌍의 개수는? 3이 아니라 6이 었던 것이다. a,b b,a b,c c,b a,c c,a

 

for (auto i : scc)
{
	if (i.size() != 1)
		ans += i.size();
}

for (auto i : scc)
{
	ll p = i.size();
	ans += p * (p - 1) / 2;
}

 

코드의 위 부분을 아래로 바꾸니 정답이 되었다.