Pagini recente » Cod sursa (job #182960) | Istoria paginii utilizator/kjasiojdias | Cod sursa (job #1996508) | Cod sursa (job #2006541) | Cod sursa (job #953984)
Cod sursa(job #953984)
/*
* Componente tare conexe
* Idee: algoritmul lui Tarjan
*/
#include <algorithm>
#include <cstdlib>
#include <fstream>
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
void dfs (int v, const vector <vector <int>> &G,
vector <int> &level, vector <int> &reach, stack <int> &visited,
vector <bool> &seen, vector <vector <int>> &components)
{
reach[v] = level[v];
seen[v] = true;
visited.push (v);
for (size_t i = 0; i < G[v].size(); ++i)
if (!seen[G[v][i]])
{
level[G[v][i]] = level[v]+1;
dfs (G[v][i], G, level, reach, visited, seen, components);
reach[v] = min (reach[v], reach[G[v][i]]);
}
else
{
reach[v] = min (reach[v], reach[G[v][i]]);
}
if (level[v] == reach[v])
{
components.push_back (vector <int>());
int x;
do {
x = visited.top();
visited.pop();
components.back().push_back (x);
} while (x != v);
}
}
int main()
{
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
int n, m;
fin >> n >> m;
vector <vector <int>> G (n+1);
for (; m; --m)
{
int x, y;
fin >> x >> y;
G[x].push_back (y);
}
vector <bool> seen (n+1, false);
vector <int> level (n+1, 0),
reach (n+1, 0);
stack <int> visited;
vector <vector <int>> components;
for (int i = 1; i <= n; ++i)
if (!seen[i])
{
dfs (i, G, level, reach, visited, seen, components);
}
fout << components.size() << endl;
for (size_t i = 0; i < components.size(); ++i)
{
for (size_t j = 0; j < components[i].size(); ++j)
fout << components[i][j] << ' ' ;
fout << endl;
}
fin.close();
fout.close();
return EXIT_SUCCESS;
}