Pagini recente » Cod sursa (job #2682643) | Cod sursa (job #792395) | Cod sursa (job #757949) | Cod sursa (job #1174768) | Cod sursa (job #2562753)
#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
#include <queue>
#include <bitset>
#include <stack>
#include <cmath>
#define MAXN 100008
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
int n, m, soll;
int used[MAXN];
vector<int> g1[MAXN],g2[MAXN],sol[MAXN];
stack<int> s;
void dfs(int nod){
used[nod] = 1;
for(int i = 0; i < g1[nod].size(); i++)
if(!used[g1[nod][i]])
dfs(g1[nod][i]);
s.push(nod);
}
void dfs2(int nod, int nr){
sol[nr].push_back(nod);
used[nod] = 1;
for(int i = 0; i < g2[nod].size(); i++)
if(!used[g2[nod][i]])
dfs2(g2[nod][i], nr);
}
void Kosarju(){
for(int i = 1; i <= n; i++)
if(!used[i])
dfs(i);
memset(used,0,sizeof(used));
for(int i = 1; i <= n; i++){
int x = s.top();
if(!used[s.top()]){
soll++;
dfs2(s.top(),soll);
}
s.pop();
}
out << soll <<'\n';
for(int i = 1; i <= soll; i++){
for(int j = 0; j < sol[i].size(); j++)
out << sol[i][j] <<" ";
out << '\n';
}
}
int main(){
in >> n >> m;
for(int i = 1; i <= m; i++){
int x, y;
in >> x >> y;
g1[x].push_back(y);
g2[y].push_back(x);
}
Kosarju();
return 0;
}