Pagini recente » Cod sursa (job #2891485) | Cod sursa (job #2121449) | Cod sursa (job #2689915) | Cod sursa (job #1971546) | Cod sursa (job #2662129)
#include <iostream>
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
ifstream in ("ctc.in");
ofstream out("ctc.out");
vector<int> graf[100005];
int low[100005],id[100005];
bool onstack[100005];
vector<vector<int>> sol;
stack<int> s;
int n,m,a,b;
int idc = 0,nr_comp = 0;
void dfs(int x)
{
id[x] = low[x] = idc++;
s.push(x);
onstack[x] = 1;
for(auto it:graf[x]){
if(id[it]==-1)
dfs(it);
if(onstack[it])
low[x] = min(low[x],low[it]);
}
if(id[x] == low[x]){
int node;
nr_comp++;
vector<int> aux;
do{
node = s.top();
aux.push_back(node);
low[node] = id[x];
s.pop();
}while(node != x);
sol.push_back(aux);
}
}
int main()
{
in>>n>>m;
for(int i=0;i<m;i++){
in>>a>>b;
graf[a-1].emplace_back(b-1);
}
for(int i=0;i<n;i++)
{
low[i] = 0;
id[i] = -1;
onstack[i] = 0;
}
for(int i=0;i<n;i++)
if(id[i]==-1)
dfs(i);
out<<nr_comp<<'\n';
for(auto it:sol){
for(auto j:it)
out<<j+1<<' ';
out<<'\n';
}
return 0;
}