Pagini recente » Cod sursa (job #3195233) | Cod sursa (job #2447646) | Cod sursa (job #2292462) | Cod sursa (job #414004) | Cod sursa (job #899230)
Cod sursa(job #899230)
#include <fstream>
#include <vector>
using namespace std;
vector <int> v[100001];
vector <int> vt[100001];
vector <int> ct[100001];
int vz[100001];
int n,m,nr;
vector <int> nodes;
void dfs(int x) {
int i;
vz[x]=1;
for (i=0; i<v[x].size(); i++)
if (!vz[v[x][i]])
dfs(v[x][i]);
nodes.push_back(x);
}
void tfs(int x) {
int i;
vz[x]=0;
for (i=0; i<vt[x].size(); i++)
if (vz[vt[x][i]])
tfs(vt[x][i]);
ct[nr].push_back(x);
}
int main() {
int i,a,b,j;
ifstream in("ctc.in");
ofstream out("ctc.out");
in>>n>>m;
for (i=1; i<=m; i++) {
in>>a>>b;
v[a].push_back(b);
vt[b].push_back(a);
}
for (i=1; i<=n; i++)
if (!vz[i])
dfs(i);
for (i=n-1; i>=0; i--)
if (vz[nodes[i]]) {
tfs(nodes[i]);
nr++;
}
out<<nr<<'\n';
for (i=0; i<nr; i++) {
for (j=0; j<ct[i].size(); j++)
out<<ct[i][j]<<' ';
out<<'\n';
}
out.close();
return 0;
}