Cod sursa(job #2970823)

Utilizator Daniel7390Popescu Daniel Daniel7390 Data 25 ianuarie 2023 22:37:57
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.79 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>


using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
stack<int> st;
int pos = -1;

void dfs_1(int s, vector<int>& vizitat, vector<vector<int>>& adj, stack<int>& st) {
    vizitat[s] = 1;
    for(auto& vecin: adj[s]) {
        if(vizitat[vecin] == 0)
            dfs_1(vecin, vizitat, adj, st);
    }
    st.push(s);
    
}

void dfs_2 (int s, vector<int>& vizitat_tr, vector<vector<int>>& adj_tr, vector<int>& componente) {
    pos++;
    vizitat_tr[s] = 1;
    componente[pos] = s;
    for(auto vecin: adj_tr[s]) {
        if(vizitat_tr[vecin] == 0) {
            dfs_2(vecin, vizitat_tr, adj_tr, componente);
        }
    }
    
}



int main()
{
    int n, m, ctc = 0;
    fin>>n>>m;
    vector<vector<int>> adj(n + 1);
    vector<vector<int>> adj_tr(n + 1);
    vector<int> vizitat(n + 1);
    vector<int> vizitat_tr(n + 1);
    vector<int> componente(2*n);
    
    
    for (int i = 0; i < m; i++) {
        
        int a, b;
        fin>>a>>b;
        adj[a].push_back(b);
        adj_tr[b].push_back(a);
        
    }
    
    for (int i = 1; i <= n; i++) {
        vizitat[i] = 0;
        vizitat_tr[i] = 0;
    }
    
    for (int i = 1; i <= n; i++)
        if(vizitat[i] == 0)
            dfs_1(i, vizitat, adj, st);
    
    while(!st.empty()) {
        int i = st.top();
        st.pop();
        if (vizitat_tr[i] == 0) {
            dfs_2(i, vizitat_tr, adj_tr, componente);
            pos++;
            ctc++;
            componente[pos] = -1;
        }
    }
    
    componente.resize(n + ctc);
    
    
    fout<<ctc<<endl;
    
    for(auto& a: componente) {
        if(a != -1)
            fout<<a<<" ";
        else
            fout<<"\n";
    }
        
        
        

     
    
    
    

    return 0;
}