Pagini recente » Cod sursa (job #299134) | Cod sursa (job #1855476) | Cod sursa (job #2731866) | Cod sursa (job #2987302) | Cod sursa (job #2868117)
#include <algorithm>
#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;
comptcon[nctc].push_back(x);
for (int i = 0; i < rG[x].size(); i++)
if (ctc[rG[x][i]] == 0)
dfs2(rG[x][i]);
}
bool comp (vector <int> a, vector <int> b)
{
return a[0] < b[0];
}
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);
comptcon.resize(1);
for (i = n - 1; i >= 0; i--)
if (ctc[order[i]] == 0)
{
nctc++;
vector <int> k;
comptcon.push_back(k);
dfs2(order[i]);
sort (comptcon[nctc].begin(), comptcon[nctc].end());
}
sort (comptcon.begin()+1, comptcon.end(), comp);
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;
}