Seletiva IOI 2013

secreto.cpp

// Ivan Carvalho
// Secreto - Seletiva IOI - OBI 2013
#include <bits/stdc++.h>
#define MAXN 100010
#define endl '\n'
using namespace std;
int visitado1[MAXN],visitado2[MAXN],grafo[MAXN],transposto[MAXN];
stack<int> pilha;
void dfs1(int x){
	//cout << "Kosaraju" << endl;
	visitado1[x] = 1;
	if (grafo[x] && !visitado1[grafo[x]]) dfs1(grafo[x]);
	pilha.push(x);
}
void dfs2(int x){
	visitado2[x] = 1;
	//cout << x << ' ';
	if (transposto[x] && !visitado2[transposto[x]]) dfs2(transposto[x]);
}
int main(){
	int forte = 0;
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	int n,contador = 0;
	cin >> n;
	map<string,int> mapa;
	for(int i=0;i<n;i++){
		string s1,s2;
		cin >> s1 >> s2;
		//cout << s1 << " " << s2 << endl;
		if (!mapa.count(s1)) mapa[s1] = ++contador;
		if (!mapa.count(s2)) mapa[s2] = ++contador;
		grafo[mapa[s1]] = mapa[s2];
		transposto[mapa[s2]] = mapa[s1];
	}
	for(int i=1;i<=contador;i++) if (!visitado1[i]) dfs1(i);
	while(!pilha.empty()){
		int i = pilha.top();
		pilha.pop();
		if (!visitado2[i]){
			forte++;
			dfs2(i);
			//cout << endl;
		}
	}
	cout << forte - 1 << endl;
	return 0;
}