Pagini recente » Cod sursa (job #1694462) | Cod sursa (job #1408411) | Cod sursa (job #69578) | Cod sursa (job #2890408) | Cod sursa (job #3232274)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m, t, cc;
vector<int>ad[100005];
vector<int>ctc[100005];
vector<int>disc;
vector<int>pr;
vector<int>vis;
vector<int>acc;
vector<int>c;
stack<int>s;
void dfs(int nod){
vis[nod]=1;
pr[nod]=1;
s.push(nod);
disc[nod]=acc[nod]=++t;
for(auto i : ad[nod]){
if(!vis[i]){
dfs(i);
acc[nod]=min(acc[nod], acc[i]);
}
else
if(pr[i])
acc[nod]=min(acc[nod], acc[i]);
}
if(acc[nod]==disc[nod]){
cc++;
while(s.top()!=nod){
pr[s.top()]=0;
ctc[cc].push_back(s.top());
s.pop();
}
pr[s.top()]=0;
ctc[cc].push_back(s.top());
s.pop();
}
}
int main(){
fin>>n>>m;
for(int i=1;i<=m;i++){
int x, y;
fin>>x>>y;
ad[x].push_back(y);
}
vis.assign(n+1, 0);
pr.assign(n+1, 0);
acc.assign(n+1, 0);
disc.assign(n+1, 0);
for(int i=1;i<=n;i++)
if(!vis[i])
dfs(i);
fout<<cc<<"\n";
for(int i=1;i<=cc;i++){
for(auto e : ctc[i])
fout<<e<<" ";
fout<<'\n';
}
return 0;
}