Pagini recente » Cod sursa (job #1170854) | Cod sursa (job #461615) | Cod sursa (job #789954) | Cod sursa (job #2717933) | Cod sursa (job #2928786)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
vector<vector<int>> graph, graph_tr;
int n, m, contor, nrs;
vector<bool> vect;
vector<int> st;
// folosim algoritmul lui Kosaraju pentru a gasit componente tari conexe
// COMPLEXITATE: O(V+E)
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector <vector <int>> rezultat;
int nrc = 0;
vector <int> level;
vector <int> st; //pentru dfs
void dfs(int k)
{
vect[k] = true;
for (auto x : graph[k])
if (!vect[x])
dfs(x);
st.push_back(k);
}
void dfs_tr(int k)
{
vect[k] = 1;
for (auto x : graph_tr[k])
if (!vect[x])
dfs_tr(x);
}
int main()
{
fin >> n >> m;
graph = graph_tr = vector<vector<int>>(n + 1);
for (int i = 1; i <= m; i++)
{
int a, b;
fin >> a >> b;
graph[a].push_back(b);
graph_tr[b].push_back(a);
}
vect = vector<bool>(n + 1, false);
for (int i = 1; i <= n; i++)
if (!vect[i])
dfs(i);
vect = vector<bool>(n + 1, false);
for (vector<int>::reverse_iterator it = st.rbegin(); it != st.rend(); it++)
if (!vect[*it])
{
contor++;
dfs_tr(*it);
}
fout << contor;
return 0;
}