Pagini recente » Cod sursa (job #711948) | Cod sursa (job #2389819) | Cod sursa (job #691699) | Cod sursa (job #1388753) | Cod sursa (job #2899875)
/// always:
#include <cstdio>
#include <string>
/// optional:
#include <cassert>
#include <cstring>
#include <iostream>
#include <vector>
#include <algorithm>
bool home = 1;
using namespace std;
const string TASKNAME="ctc";
const int N=100000+7;
int n;
int m;
bool vis[N];
vector<int> g[N];
vector<int> ig[N];
vector<int> ord;
void dfs(int a) {
if (vis[a]) return;
vis[a]=1;
for (auto &b:g[a]) {
dfs(b);
}
ord.push_back(a);
}
vector<int> cur;
void invdfs(int a) {
if(vis[a]) return;
vis[a]=1;
cur.push_back(a);
for (auto &b:ig[a]) {
invdfs(b);
}
}
signed main() {
#ifdef INFOARENA
home = 0;
#endif
if(!home) {
freopen((TASKNAME + ".in").c_str(), "r", stdin);
freopen((TASKNAME + ".out").c_str(), "w", stdout);
}else{
freopen ("I_am_iron_man", "r", stdin);
}
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++) {
int a,b;
scanf("%d%d",&a,&b);
g[a].push_back(b);
ig[b].push_back(a);
}
for (int i=1;i<=n;i++) {
dfs(i);
}
reverse(ord.begin(),ord.end());
for (int i=1;i<=n;i++) {
vis[i]=0;
}
vector<vector<int>> sol;
for (auto &i:ord) {
if(vis[i]) continue;
cur.clear();
invdfs(i);
sol.push_back(cur);
}
printf("%d\n",(int)sol.size());
for (auto &v:sol) {
for (auto &x:v) {
printf("%d ", x);
}
printf("\n");
}
}