Pagini recente » Cod sursa (job #2180316) | Cod sursa (job #2264607) | Cod sursa (job #2291208) | Cod sursa (job #2700244) | Cod sursa (job #3166630)
#include <bits/stdc++.h>
#define NM 100001
using namespace std;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
vector <int> g[NM], gt[NM], ctc[NM];
int n, m, contor, k, viz[NM], z[NM], nrc;
void dfs (int x)
{
int w, j;
viz[x] = 1;
for (j = 0; j < g[x].size(); j++)
{
w = g[x][j];
if (viz[w] == 0)
dfs(w);
}
k++;
z[k] = x;
}
void dfst (int x)
{
int w, j;
viz[x] = 1;
ctc[nrc].push_back(x);
for (j = 0; j < gt[x].size(); j++)
{
w = gt[x][j];
if (viz[w] == 0)
dfst(w);
}
}
int main()
{
fin >> n >> m;
int i, a, b;
for (i = 1; i <= m; i ++)
{
fin >> a >> b;
g[a].push_back(b);
gt[b].push_back(a);
}
for (i = 1; i <= n; i ++)
if (viz[i] == 0)
dfs(i);
for (i = 1; i <= n; i ++)
viz[i] = 0;
for (i = n; i >= 1; i --)
if (viz[z[i]] == 0)
{
nrc ++;
dfst(z[i]);
}
fout << nrc << '\n';
for (i = 1; i <= nrc; i ++)
{
for (int j = 0; j < ctc[i].size(); j ++)
fout << ctc[i][j] << ' ';
fout << '\n';
}
return 0;
}