[백준] 2668 숫자고르기

문제

세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절히 뽑으면, 그 뽑힌 정수들이 이루는 집합과, 뽑힌 정수들의 바로 밑의 둘째 줄에 들어있는 정수들이 이루는 집합이 일치한다. 이러한 조건을 만족시키도록 정수들을 뽑되, 최대로 많이 뽑는 방법을 찾는 프로그램을 작성하시오. 예를 들어, N=7인 경우 아래와 같이 표가 주어졌다고 하자.

이 경우에는 첫째 줄에서 1, 3, 5를 뽑는 것이 답이다. 첫째 줄의 1, 3, 5밑에는 각각 3, 1, 5가 있으며 두 집합은 일치한다. 이때 집합의 크기는 3이다. 만약 첫째 줄에서 1과 3을 뽑으면, 이들 바로 밑에는 정수 3과 1이 있으므로 두 집합이 일치한다. 그러나, 이 경우에 뽑힌 정수의 개수는 최대가 아니므로 답이 될 수 없다.

입력

첫째 줄에는 N(1≤N≤100)을 나타내는 정수 하나가 주어진다. 그 다음 줄부터는 표의 둘째 줄에 들어가는 정수들이 순서대로 한 줄에 하나씩 입력된다.

출력

첫째 줄에 뽑힌 정수들의 개수를 출력하고, 그 다음 줄부터는 뽑힌 정수들을 작은 수부터 큰 수의 순서로 한 줄에 하나씩 출력한다.

 

사이클이 있는지 확인하는 문제입니다.

한 정점이 그 저점 스스로를 가리키는 것도 사이클로 포함합니다.

 

타잔알고리즘을 사용해 응용하였습니다.

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false),cin.tie(NULL);
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[] = { -1,0,1,0 }, dx[] = { 0,1,0,-1 }, INF = 987654321;

using namespace std;
int N, v[101], s[101], cnt, p[101], num, ans;
vi adj[101], st;
vvi cycle;
int dfs(int k) {
	st.push_back(k);
	int parent = v[k] = ++cnt;
	if (!v[p[k]]) {
		parent = min(parent, dfs(p[k]));
	}
	if (!s[p[k]]) {
		parent = min(parent, v[p[k]]);
	}
	if (parent == v[k]) {
		vi temp;
		while (1) {
			int t = st.back();
			temp.push_back(t);
			st.pop_back();
			s[t] = 1;
			if (t == k)break;
		}
		cycle.push_back(temp);
	}
	return parent;
}
int main() {
	FAST;
	cin >> N;
	REP(i, N) {
		cin >> p[i];
	}
	REP(i, N) {
		if (!v[i])dfs(i);
	}
	vi answer;
	for (vi temp : cycle) {
		if (temp.size() != 1) {
			for (int r : temp)answer.push_back(r);
		}
		else {
			if (temp[0] == p[temp[0]])answer.push_back(temp[0]);
		}
	}
	sort(answer.begin(), answer.end());
	cout << answer.size() << "\n";
	for (int r : answer)cout << r << "\n";
}