Pagini recente » Cod sursa (job #311159) | Cod sursa (job #2906339) | Cod sursa (job #2759235) | Cod sursa (job #1668330) | Cod sursa (job #3198431)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n,m,x,y,inS[100001],dfn[100001],low[100001],nrc,cnt;
vector<int>g[100001],c;
vector<vector<int> >rez;
stack<int>s;
void tarjan(int k){
dfn[k]=low[k]=++cnt;
s.push(k);
inS[k]=1;
for(int i:g[k]){
if(!dfn[i]){
tarjan(i);
low[k]=min(low[k],low[i]);
}
else{
if(inS[i]){
low[k]=min(low[k],dfn[i]);
}
}
}
if(low[k]==dfn[k]){
nrc++;
c.clear();
while(true){
int val=s.top();
s.pop();
inS[val]=0;
c.push_back(val);
if(val==k)break;
}
rez.push_back(c);
}
}
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(!dfn[i]){
cnt=0;
tarjan(i);
}
}
fout<<nrc<<'\n';
for(int i=0;i<rez.size();i++){
sort(rez[i].begin(),rez[i].end());
}
for(int i=0;i<rez.size();i++){
for(int j=0;j<rez[i].size();j++){
fout<<rez[i][j]<<' ';
}
fout<<'\n';
}
}