Cod sursa(job #2928807)

Utilizator readyitzooDilirici Mihai readyitzoo Data 23 octombrie 2022 22:00:05
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.65 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");

vector<vector<int>> graph;
vector<vector<int>> graph_t;
int index=1;
stack <int> S;
queue <int> Q;
vector<int> visited;

void DFS_t(vector<vector<int>> graph_t, int n, int x, int index){
    visited[x]=index;
    for(int i = 0; i < graph_t[x].size(); i ++){
        if(visited[graph_t[x][i]] == 0){
            DFS_t(graph_t, n, graph_t[x][i], index);
        }
    }
    S.push(x);
}

void DFS(vector<vector<int>> graph, int n, int x){
    visited[x] = index;
    for(int i = 0; i < graph[x].size(); i ++){
        if(visited[graph[x][i]] == 0){
            DFS(graph, n, graph[x][i]);
        }
    }
    S.push(x);
}



int main() {
    int n, m;

    f >> n >> m;
    graph.resize(n+1);
    graph_t.resize(n+1);
    visited.resize(n+1);
    for(int i = 0; i < m; i ++){
        int x, y;
        f >> x >> y;
        graph[x].push_back(y);
        graph_t[y].push_back(x);
    }

    for(int i = 1; i <= n;i ++){
        if(visited[i] == 0){
            DFS(graph, n, i);
        }
    }

    for(int i = 1; i <= n; i ++){
        visited[i] = 0;
    }
    while(!S.empty()){
        int x=S.top();
        S.pop();
        if(visited[x] == 0){
            DFS_t(graph_t, n, x, index);
            for(int i = 1; i <= n; i++){
                if(visited[i] == index){
                    Q.push(i);
                }
            }
            Q.push(-1);
            index += 1;
        }
    }
    g << index - 1 << endl;
    while(!Q.empty()){
        int x=Q.front();
        Q.pop();
        if (x != -1)
            g << x << " ";
        else
            g << endl;
    }

    return 0;
}