Cod sursa(job #2668414)

Utilizator MARIAN.DANAILADanaila Marian MARIAN.DANAILA Data 4 noiembrie 2020 21:13:48
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include<bits/stdc++.h>
#define N 100005
using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

int visited[N], visited_t[N], scc;
vector <int> edges[N];
vector <int> edges_t[N];
vector <int> solution[N];
stack <int> s;

void dfs(int vertex){
    int i;
    visited[vertex] = 1;
    for(i = 0;i < edges[vertex].size();i++){
        if(!visited[edges[vertex][i]]){
            dfs(edges[vertex][i]);
        }
    }
    s.push(vertex);
}

void dfs_t(int vertex){
    int i;
    visited_t[vertex] = 1;
    solution[scc].push_back(vertex);
    for(i = 0;i < edges_t[vertex].size();i++){
        if(!visited_t[edges_t[vertex][i]]){
            dfs_t(edges_t[vertex][i]);
        }
    }

}

int main()
{
    int n, m, x, y, i, j;
    fin>>n>>m;
    for(i=1;i<=m;i++){
        fin>>x>>y;
        edges[x].push_back(y);
        edges_t[y].push_back(x);
    }

    for(i = 1;i <= n;i++){
        if(!visited[i]){
            dfs(i);
        }
    }
    while(!s.empty()){
        if(!visited_t[s.top()]){
            scc++;
            dfs_t(s.top());
        }
        s.pop();
    }

    fout<<scc<<endl;
    for(i = 1;i <= scc;i++){
        for(j = 0;j < solution[i].size();j++){
            fout<<solution[i][j]<<" ";
        }
        fout<<endl;
    }

    return 0;
}