Pagini recente » Cod sursa (job #398041) | Cod sursa (job #391880) | Cod sursa (job #470263) | Cod sursa (job #2360991) | Cod sursa (job #3252932)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
//#include <bits/stdc++.h>
#define in fin
#define out fout
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector< int > v[100001], vt[100001];
vector< int > st;
bool vis[100001];
vector< vector<int> > ctc;
void dfs(int nod, int t){
if(t == 0){ // facem ST pe graful ne-transpus
vis[nod] = 1;
for(int i = 0; i < v[nod].size(); i++){
if(!vis[ v[nod][i] ]) dfs( v[nod][i], t );
}
st.push_back( nod );
}else{
vis[nod] = 1;
ctc.back().push_back(nod);
for(int i = 0; i < vt[nod].size(); i++){
if(!vis[ vt[nod][i] ]){
dfs(vt[nod][i], t);
}
}
}
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m; in >> n >> m;
for(int i = 0; i < m; i++){
int a, b; in >> a >> b;
v[a].push_back(b);
vt[b].push_back(a);
}
for(int i = 1; i <= n; i++){
if(vis[i] == 0) dfs(i, 0);
}
// cout << "ST : ";
// for(int i = 0; i < st.size(); i++) cout << st[i] << " ";
// cout << '\n';
for(int i = 0; i <= 100000; i++) vis[i] = 0;
for(int i = st.size() - 1; i >= 0; i--){
if(!vis[ st[i] ]){
vector<int> l;
ctc.push_back(l);
dfs(st[i], 1);
}
}
// cout << "ctc : \n";
out << ctc.size() << '\n';
for(int i = 0; i < ctc.size(); i++){
sort( ctc[i].begin(), ctc[i].end() );
for(int j = 0; j < ctc[i].size(); j++) out << ctc[i][j] << " ";
out << '\n';
}
return 0;
}