Pagini recente » Cod sursa (job #2158154) | Cod sursa (job #1971166) | Cod sursa (job #2933392) | Cod sursa (job #2274513) | Cod sursa (job #2816184)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
vector <int> h[100003];
vector <int> g[100003];
vector <int> scc[100003]; /// strongly conn. comp.
int n, m, nrc;
int st[100003], viz[100003], top;
void DFS(int n)
{
viz[n] = 1;
for (int i : h[n])
if (viz[i] == 0)
DFS(i);
st[++top] = n;
}
/// viz[i] = 1 , pt orice i de la 1 la n, astfel consideram viz[i] = 1 -> nevizitat
/// viz[i] = 0 -> vizitat, pentru a nu reinitializa vectorul viz
void DFS2(int n)
{
viz[n] = 0;
for (int i : g[n])
if (viz[i] == 1)
DFS2(i);
scc[nrc].push_back(n);
}
void SCC()
{
for (int i = 1; i <= n; i++)
if (viz[i] == 0)
DFS(i);
for (int i = n; i > 0; i--)
if (viz[st[i]] == 1)
{
nrc++;
DFS2(st[i]);
}
}
void Afis()
{
fout << nrc << "\n";
for (int i = 1; i <= nrc; i++)
{
for (int j : scc[i])
fout << j << " ";
fout << "\n";
}
}
int main()
{
fin >> n >> m;
for (int i = 1; i <= m; i++)
{
int x , y;
fin >> x >> y;
h[x].push_back(y);
g[y].push_back(x);
}
SCC();
Afis();
return 0;
}