Cod sursa(job #2645867)

Utilizator silviu982001Borsan Silviu silviu982001 Data 29 august 2020 19:47:54
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.48 kb
#include <fstream>
#include <vector>
#include <unordered_set>
#include <stack>

#define NMAX 100001

using namespace std;

vector<int> G[NMAX], GT[NMAX];
unordered_set<int> viz;
stack<int> st;
vector<vector<int>> result;

int n, m;

void DFS(int nod)
{
    viz.insert(nod);
    
    for (const int& vec : G[nod])
        if (viz.find(vec) == viz.end())
            DFS(vec);
    
    st.push(nod);
}

void DFST(int nod, vector<int>& v)
{
    viz.insert(nod);
    
    v.push_back(nod);
    
    for (const int& vec : GT[nod])
        if (viz.find(vec) == viz.end())
            DFST(vec, v);
}


int main(int argc, const char * argv[]) {
    
    ifstream fin("ctc.in");
    fin >> n >> m;
    int x, y;
    
    for (int i = 0; i < m; ++i)
    {
        fin >> x >> y;
        G[x].push_back(y);
        GT[y].push_back(x);
    }
    
    fin.close();
    
    for (int nod = 1; nod <= n; ++nod)
        if (viz.find(nod) == viz.end())
            DFS(nod);
    
    viz.clear();
    
    for (; !st.empty(); )
    {
        int nod = st.top();
        st.pop();
        
        if (viz.find(nod) != viz.end())
            continue;
        
        vector<int> v;
        
        DFST(nod, v);
        
        result.push_back(v);
    }
    
    ofstream fout("ctc.out");
    
    fout << result.size() << '\n';
    
    for (int i = 0; i < result.size(); ++i)
    {
        for (const int& nod : result[i])
            fout << nod << ' ';
        fout << '\n';
    }
    
    fout.close();
    
    return 0;
}