Pagini recente » Arhiva educaţională | Arhiva Educationala | Cod sursa (job #383102) | Cod sursa (job #3291991) | Cod sursa (job #3285903)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m, viz[100003], v[100003], len, nrctc;
vector<int> l[100003], g[100003];
void Citire()
{
int i, j, p;
fin >> n >> m;
for (p = 1; p <= m; p++)
{
fin >> i >> j;
l[i].push_back(j);
g[j].push_back(i);
}
}
void DFS_TF(int x)
{
viz[x] = 1;
for (int i : l[x])
if (viz[i] == 0) DFS_TF(i);
v[++len] = x;
}
void SortTop()
{
for (int i = 1; i <= n; i++)
if (viz[i] == 0) DFS_TF(i);
}
void DFS(int x)
{
viz[x] = nrctc;
for (int i : g[x])
if (viz[i] == 0) DFS(i);
}
void Kosaraju()
{
int i, j, k;
SortTop();
for (i = 1; i <= n; i++)
viz[i] = 0;
for (i = n; i >= 1; i--)
{
k = v[i];
if (viz[k] == 0)
{
nrctc++;
DFS(k);
}
}
fout << nrctc << "\n";
for (i = 1; i <= nrctc; i++)
{
for (j = 1; j <= n; j++)
if (viz[j] == i) fout << j << " ";
fout << "\n";
}
}
int main()
{
Citire();
Kosaraju();
return 0;
}
//0, 1, 3-5, 7-18, 21, 22, 24-27, 29, 30, 34-36, 42, 44, 45, 47, 48, 51, 54, 56-58