Pagini recente » Cod sursa (job #1252978) | Cod sursa (job #1996168) | Cod sursa (job #1697488) | Cod sursa (job #1633755) | Cod sursa (job #2313352)
#include <bits/stdc++.h>
using namespace std;
#define LMAX 100005
vector<int> G[LMAX],GT[LMAX];
bool Plus[LMAX];
int Minus[LMAX];
vector<int> CTC[LMAX];
stack<int> st;
int ctc=0;
void DFS1(int n){
Plus[n]=1;
for(auto it : G[n])
if(!Plus[it])
DFS1(it);
st.push(n);
}
void DFS2(int n){
CTC[ctc].push_back(n);
Minus[n]=ctc;
for(auto it : GT[n])
if(!Minus[it])
DFS2(it);
}
int n,m;
void Kosaraju(){
for(int i=1;i<=n;++i)
if(!Plus[i])
DFS1(i);
while(!st.empty()){
int x=st.top();
st.pop();
if(!Minus[x]){
++ctc;
DFS2(x);
}
}
printf("%d\n",ctc);
for(int i=1;i<=ctc;++i){
for(auto it: CTC[i])
printf("%d ",it);
printf("\n");
}
}
int main(){
// freopen("ctc.in","r",stdin);
// freopen("ctc.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=m;++i){
int st,dr;
scanf("%d %d",&st,&dr);
G[st].push_back(dr);
GT[dr].push_back(st);
}
Kosaraju();
return 0;
}