Cod sursa(job #2313353)

Utilizator Vlad3108Tir Vlad Ioan Vlad3108 Data 6 ianuarie 2019 18:27:01
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#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;
}