Cod sursa(job #2928786)

Utilizator AntoniaPopoviciAntonia-Adelina Popovici AntoniaPopovici Data 23 octombrie 2022 21:11:51
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

vector<vector<int>> graph, graph_tr;

int n, m, contor, nrs;

vector<bool> vect;
vector<int> st;

// folosim algoritmul lui Kosaraju pentru a gasit componente tari conexe
// COMPLEXITATE: O(V+E)

ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector <vector <int>> rezultat;
int nrc = 0;
vector <int> level;
vector <int> st; //pentru dfs

void dfs(int k)
{
    vect[k] = true;
    for (auto x : graph[k])
        if (!vect[x])
            dfs(x);
    st.push_back(k);
}

void dfs_tr(int k)
{
    vect[k] = 1;
    for (auto x : graph_tr[k])
        if (!vect[x])
            dfs_tr(x);
}

int main()
{
    fin >> n >> m;
    graph = graph_tr = vector<vector<int>>(n + 1);
    for (int i = 1; i <= m; i++)
    {
        int a, b;
        fin >> a >> b;
        graph[a].push_back(b);
        graph_tr[b].push_back(a);
    }

    vect = vector<bool>(n + 1, false);
    for (int i = 1; i <= n; i++)
        if (!vect[i])
            dfs(i);

    vect = vector<bool>(n + 1, false);
    for (vector<int>::reverse_iterator it = st.rbegin(); it != st.rend(); it++)
        if (!vect[*it])
        {
            contor++;
            dfs_tr(*it);
        }

    fout << contor;
    return 0;
}