Pagini recente » Cod sursa (job #56555) | Cod sursa (job #444501) | Cod sursa (job #1927133) | Cod sursa (job #1100915) | Cod sursa (job #2868125)
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m, i, j, x, y, nctc;
vector <vector <int>> G, rG, comptcon;
vector <int> viz, ctc, order;
void dfs1(int x)
{
viz[x] = 1;
for (int i = 0; i < G[x].size(); i++)
if (viz[G[x][i]] == 0)
dfs1(G[x][i]);
order.push_back(x);
}
void dfs2(int x)
{
ctc[x] = nctc;
for (int i = 0; i < rG[x].size(); i++)
if (ctc[rG[x][i]] == 0)
dfs2(rG[x][i]);
}
int main()
{
fin >> n >> m; G.resize(n + 1), rG.resize(n + 1), viz.resize(n + 1), ctc.resize(n + 1);
for (i = 1; i <= m; i++)
{
fin >> x >> y;
G[x].push_back(y);
rG[y].push_back(x);
}
for (i = 1; i <= n; i++)
if (viz[i] == 0)
dfs1(i);
for (i = n - 1; i >= 0; i--)
if (ctc[order[i]] == 0)
{
nctc++;
dfs2(order[i]);
}
comptcon.resize(nctc+1);
for (i = 1; i <= n; i++)
comptcon[ctc[i]].push_back(i);
fout << nctc << '\n';
for (i = 1; i <= nctc; i++)
{
for (j = 0; j < comptcon[i].size(); j++)
fout << comptcon[i][j] << ' ';
fout << '\n';
}
return 0;
}