Pagini recente » Cod sursa (job #2641045) | Cod sursa (job #1360873) | Cod sursa (job #647303) | Istoria paginii runda/ceau_oni2017_3/clasament | Cod sursa (job #3300859)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
int n, m, x, y, time, nr;
vector<int> L[100002], L2[100002], v, comp[100002];
bool viz[100002], viz2[100002];
void dfs(int nod){
//time++;
viz[nod]=1;
for(int i=0;i<L[nod].size();i++){
int vecin=L[nod][i];
if(!viz[vecin]){
dfs(vecin);
}
}
//time++;
v.push_back(nod);
}
void dfs2(int nod){
viz2[nod]=1;
comp[nr].push_back(nod);
for(int i=0;i<L2[nod].size();i++){
int vecin=L2[nod][i];
if(!viz2[vecin]){
dfs2(vecin);
}
}
}
int main() {
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>x>>y;
L[x].push_back(y);
L2[y].push_back(x);
}
for(int i=1;i<=n;i++){
if(!viz[i])
dfs(i);
}
reverse(v.begin(), v.end());
//time=0;
for(int i=0;i<n;i++){
if(!viz2[v[i]]){
nr++;
dfs2(v[i]);
}
}
cout<<nr<<"\n";
for(int i=1;i<=nr;i++){
for(int j=0;j<comp[i].size();j++)
cout<<comp[i][j]<<" ";
cout<<"\n";
}
}