Pagini recente » Cod sursa (job #2426033) | Cod sursa (job #488955) | Cod sursa (job #2272967) | Profil liviur | Cod sursa (job #2209284)
#include <bits/stdc++.h>
using namespace std;
ofstream fout("ctc.out");
ifstream fin("ctc.in");
#define NMAX 100005
vector<vector<int> > sol;
vector<int> G[NMAX];
int comp[NMAX];
int level[NMAX];
stack<int> st;
bool inStack[NMAX];
int n, m, x, y;
int indexi;
void dfs(int node){
comp[node] = ++indexi;
level[node] = indexi;
inStack[node] = true;
st.push(node);
indexi++;
for(auto next : G[node]){
if(!comp[next]) dfs(next), level[node] = min(level[node], level[next]);
else if(inStack[next]) level[node] = min(level[node], level[next]);
}
if(comp[node] == level[node]){
sol.push_back(vector<int>());
int v;
do{
v = st.top();
sol[sol.size() - 1].push_back(v);
inStack[v] = false;
st.pop();
}while(v != node);
}
}
int main()
{
fin >> n >> m;
for(int i = 1; i <= m; i++){
fin >> x >> y;
G[x].push_back(y);
}
for(int i = 1; i <= n; i++){
if(comp[i] == 0)
dfs(i);
}
fout << sol.size()<< '\n';
for(int i = 0; i < sol.size(); i++){
for(int j = 0; j < sol[i].size(); j++){
fout << sol[i][j] << " ";
}
fout << endl;
}
return 0;
}