Cod sursa(job #2864368)

Utilizator Calin453Bantas Calin Andrei Calin453 Data 7 martie 2022 20:16:07
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.76 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
vector<int>a[100005];
vector<int>a2[100005];
int viz[100005];
int viz2[100005];
int viz3[100005];
int cnt, cnt2;
int n, m;
int rasp[100005];
void dfs(int x)
{
    viz[x] = 1;
    for(int i = 0; i < a[x].size() ; i++)
    {
        //cout << i << " " << a[x][i] << " ";
        if(viz[a[x][i]] == 0)
        {
            dfs(a[x][i]);
        }
    }
    rasp[cnt] = x;
    cnt++;

}

void dfs2(int x)
{
    viz2[x] = 1;
    for(int i = 0; i < a2[x].size() ; i++)
    {
        if(viz2[a2[x][i]] == 0)
        {
            dfs2(a2[x][i]);
        }
    }

}

void dfs3(int x)
{
    out << x << " ";
    viz3[x] = 1;
    for(int i = 0; i < a2[x].size() ; i++)
    {
        if(viz3[a2[x][i]] == 0)
        {
            dfs3(a2[x][i]);
        }
    }

}


int main()
{
    int x, y;
    in >> n >> m;

    for(int i = 1; i <= m; i++)
    {
        in >> x >> y;
        a[x].push_back(y);
        a2[y].push_back(x);
    }

    for(int i = 1; i <= n; i++)
    {
        if(viz[i] == 0)
        {
            dfs(i);
        }
    }

    for(int i = cnt - 1; i >= 0; i--)
    {
        if(viz2[rasp[i]] == 0)
        {
            cnt2++;
            dfs2(rasp[i]);
        }
    }

    out << cnt2 << "\n";

    for(int i = cnt - 1; i >= 0; i--)
    {
        if(viz3[rasp[i]] == 0)
        {
            dfs3(rasp[i]);
            out << "\n";
        }
    }

    return 0;
}

/*
algoritim

iti creezi si graful transpus (muchiile au directie inversa)
faci sortare topologica pe graful normal
parcurgi nodurile sortate topologic si faci dfs pe graful transpus ca la algoritmul de componente conexe
*/