Pagini recente » Cod sursa (job #1330694) | Monitorul de evaluare | Cod sursa (job #1718087) | Cod sursa (job #1702195) | Cod sursa (job #2146041)
#include <fstream>
#include <stack>
#include <vector>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
const int MAXN = 100005;
#define Min(a, b) ((a) < (b) ? (a) : (b))
vector < int > adj[MAXN], d, low, in_stack, C[MAXN];
stack < int > S;
int ordine, n, con;
void Citire()
{
int m, x, y;
cin >> n >> m;
while( m ) cin >> x >> y, adj[x].push_back(y), -- m;
}
void Afisare()
{
cout << con << "\n";
for (int i = 0; i < con; ++ i)
{
for (int j = 0; j < C[i].size(); ++ j) cout << C[i][j] << ' ';
cout << '\n';
}
}
void Tarjan(int n)
{
d[n] = low[n] = ordine++;
S.push(n), in_stack[n] = 1;
int v;
for (int i = 0; i < adj[n].size(); ++ i)
{
v = adj[n][i];
if (d[v] == -1) Tarjan(v), low[n] = Min(low[n], low[v]);
else if (in_stack[v]) low[n] = Min(low[n], low[v]);
}
if (d[n] == low[n]) {
int node;
do {
node = S.top();
C[con].push_back(node);
S.pop(), in_stack[node] = 0;
}
while (node != n);
con++;
}
}
void SCC()
{
d.resize(n + 1), low.resize(n + 1), in_stack.resize(n + 1);
d.assign(n + 1, -1), in_stack.assign(n + 1, 0);
for (int i = 1; i <= n; ++ i) if (d[i] == -1) Tarjan(i);
}
int main()
{
Citire();
SCC();
Afisare();
}