Pagini recente » Cod sursa (job #1683387) | Cod sursa (job #104444) | Monitorul de evaluare | Cod sursa (job #190011) | Cod sursa (job #361666)
Cod sursa(job #361666)
#include <iostream>
#include <fstream>
#include <vector>
#define MAXN 100010
using namespace std;
vector<vector<int> > Ans;
vector<int> G[MAXN];
vector<int> GT[MAXN];
int vis[MAXN];
int postordine[MAXN],nr;
int N,M;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int read() {
int x,y;
int i;
fin >> N >> M;
for (i=0;i<M;++i) {
fin >> x >> y;
x--;y--;
G[x].push_back(y);
GT[y].push_back(x);
}
}
int DFS(int x) {
int i;
vis[x] = 1;
for (i=0;i<G[x].size();++i) {
if (!vis[G[x][i]]) DFS(G[x][i]);
}
postordine[nr++] = x;
}
int DFST(int x,int k) {
int i;
vis[x] = 0;Ans[k].push_back(x);
for (i=0;i<GT[x].size();++i) {
if (vis[GT[x][i]]) DFST(GT[x][i],k);
}
}
int solve() {
int i,nrc;
nrc = 0;
memset(vis,0,sizeof(vis));
for (i=0;i<N;++i) {
if (!vis[i]) DFS(i);
}
for (i=N-1;i>=0;--i) {
if (vis[postordine[i]]) {
Ans.push_back(vector<int>());
DFST(postordine[i],nrc);
nrc++;
}
}
}
int write() {
int i,j;
fout << Ans.size() << "\n";
for (i=0;i<Ans.size();++i) {
for (j=0;j<Ans[i].size();++j) fout << Ans[i][j] + 1 << " ";
fout << "\n";
}
}
int main() {
read();
solve();
write();
fin.close();
fout.close();
return 0;
}