Pagini recente » Cod sursa (job #291200) | Cod sursa (job #1477559) | Cod sursa (job #990286) | Cod sursa (job #2523782) | Cod sursa (job #2320661)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector<int>vp[100000];
vector<int>vpinv[100000];
vector<int>rez[100000];
vector<pair<int,int> >times;
bool vf[10000];
int time = 0;
void resetvf(int n){
for(int i=0; i<=n; i++)vf[i] = 0;
}
void DFSinv(int x){
vf[x] = 1;
time++;
for(int i=0; i<vpinv[x].size(); i++){
if(vf[ vpinv[x][i] ] == 0){
DFSinv(vpinv[x][i]);
}
}
time++;
times.push_back(make_pair(time,x));
}
void DFSnorm(int x,int sols){
vf[x] = 1;
//cout<<x<<' ';
rez[sols].push_back(x);
for(int i=0; i<vp[x].size(); i++){
if(vf[vp[x][i]] == 0){
DFSnorm(vp[x][i], sols);
}
}
}
int main(){
int n,m,a,b;
fin>>n>>m;
for(int i=0; i<m; i++){
fin>>a>>b;
vp[a].push_back(b);
vpinv[b].push_back(a);
}
for(int i=1; i<=n; i++)
if(vf[i]==0)
DFSinv(i);
sort(times.begin(), times.end(), greater<pair<int,int> >());
resetvf(n);
int sols=0;
for(int i=0; i<times.size(); i++){
if(vf[times[i].second] == 0){
DFSnorm(times[i].second, sols);
//fout<<'\n';
sols++;
}
}
fout<<sols<<'\n';
for(int i=0; i<sols; i++){
for(int j=0; j<rez[i].size(); j++){
fout<<rez[i][j]<<' ';
}
fout<<'\n';
}
}