Pagini recente » Cod sursa (job #1956741) | Cod sursa (job #3208421) | Cod sursa (job #144997) | Cod sursa (job #3296195)
#include <bits/stdc++.h>
#define in fin
#define out fout
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector<int> g[20000], gt[20000];
bool m[20000];
vector<int> st;
vector< vector<int> > ctc;
void dfs(int nod, int f, bool care){
m[nod] = 1;
if(care == 0){ // st
for(const int & x : g[nod]){
if(!m[x]){
m[x] = 1;
dfs(x, nod, care);
}
}
st.push_back(nod);
}else{
if(f == -1) ctc.push_back({});
ctc.back().push_back(nod);
for(const int & x : gt[nod]){
if(!m[x]){
m[x] = 1;
dfs(x, nod, care);
}
}
}
}
int main()
{
int n, _m; in >> n >> _m;
for(int i = 0; i < _m; i++){
int a, b; in >> a >> b;
g[a].push_back(b);
gt[b].push_back(a);
}
dfs(1, -1, 0);
/*cout << "st : ";
for(int i = 0; i < st.size(); i++) cout << st[i] << " ";
cout << '\n';*/
for(int i = 0; i <= n; i++) m[i] = 0;
for(int i = st.size() - 1; i >= 0; i--){
if(m[ st[i] ]) continue;
dfs(st[i], -1, 1);
}
out << ctc.size() << '\n';
for(int i = 0; i < ctc.size(); i++){
for(int j = 0; j < ctc[i].size(); j++) out << ctc[i][j] << " ";
out << '\n';
}
return 0;
}
/*
5 4
1 2
2 3
1 3
5 4
*/