Pagini recente » Cod sursa (job #2361715) | Cod sursa (job #894693) | Cod sursa (job #2082252) | Cod sursa (job #1356156) | Cod sursa (job #602500)
Cod sursa(job #602500)
#include <fstream>
#include <vector>
#include <string.h>
#define max_n 100001
using namespace std;
int i,n,m,x,y,nst,rez;
vector <int> g[max_n];
vector <int> gt[max_n];
vector <int>::iterator it;
bool u[max_n];
int st[max_n];
vector <int> sol[max_n];
ifstream in("ctc.in");
ofstream out("ctc.out");
void DF1(int x) {
vector <int>::iterator it;
u[x]=true;
for (it=g[x].begin(); it!=g[x].end(); it++)
if (!u[*it]) DF1(*it);
st[nst++]=x;
}
void DF2(int x) {
vector <int>::iterator it;
u[x]=true;
sol[rez].push_back(x);
for (it=gt[x].begin(); it!=gt[x].end(); it++)
if (!u[*it]) DF2(*it);
}
int main () {
in >> n >> m;
for (i=1; i<=m; i++) {
in >> x >> y;
g[x].push_back(y);
gt[y].push_back(x);
}
nst=rez=0;
memset(u,false,sizeof(u));
for (i=1; i<=n; i++)
if (!u[i])
DF1(i);
memset(u,false,sizeof(u));
for (i=n-1; i>=0; i--)
if (!u[st[i]]) {
DF2(st[i]);
rez++;
}
out << rez << '\n';
for (i=0; i<rez; i++) {
for (it=sol[i].begin(); it!=sol[i].end(); it++)
out << *it << ' ';
out << '\n';
}
return 0;
}