Pagini recente » Cod sursa (job #2149479) | Cod sursa (job #268482) | Cod sursa (job #2800524) | Cod sursa (job #1006575) | Cod sursa (job #1971540)
#include <bits/stdc++.h>
using namespace std;
vector <int> graf[100001];
vector <int> graf_inversat[100001];
bool viz[100001];
vector <int> v;
vector <int> componente[100001];
int cate_componente;
void dfs1 (int nod)
{
viz[nod] = 1;
for (auto x:graf[nod])
if (viz[x]==0)
dfs1(x);
v.push_back(nod);
}
void dfs2 (int nod)
{
componente[cate_componente].push_back(nod);
viz[nod] = 0;
for (auto x:graf_inversat[nod])
if (viz[x])
dfs2(x);
}
int main()
{
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
int n, m;
fin >> n >> m;
for (int i = 1; i<=m; ++i)
{
int x, y;
fin >> x >> y;
graf[x].push_back(y);
graf_inversat[y].push_back(x);
}
for (int i = 1; i<=n; ++i)
if (viz[i] == 0)
dfs1(i);
for (int i = n-1; i>=0; --i)
if (viz[v[i]])
{
cate_componente++;
dfs2(v[i]);
}
fout << cate_componente << '\n';
for (int i = 1; i<=cate_componente; ++i)
{
sort(componente[i].begin(), componente[i].end());
for (auto x:componente[i])
fout << x << " ";
fout << '\n';
}
return 0;
}