Cod sursa(job #2665382)

Utilizator anacomoAna-Maria Comorasu anacomo Data 30 octombrie 2020 17:36:44
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.6 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

int culoare;
vector <int> rezultat[10000000];

void DFS1(int current, vector <bool>& visited, vector <int> fii[])
{
    visited[current] = 1;
    for(int j = 0; j < fii[current].size(); ++j)
    {
        if(visited[fii[current][j]] == false)
            DFS1(fii[current][j], visited, fii);
    }
}

void DFS2(int node, vector <bool>& visited, vector <int> parinti[])
{
    visited[node] = 1;
    rezultat[culoare].push_back(node);
    {
        for(int i = 0; i <= parinti[node].size(); ++i)
            if(visited[parinti[node][i]] == 0)
                DFS2(parinti[node][i], visited, parinti);
    }
}

// Kosaraju
int main()
{
    int n, m;

    vector <int> fii[n+1];
    vector <int> parinti[n+1];

    fin >> n >> m;
    for(int i = 0; i < m; ++i)
    {
        int x, y;
        fin >> x >> y;
        fii[x].push_back(y);
        parinti[y].push_back(x);
    }

    vector <bool> visited(n+1, 0);
    stack <int> stiva;

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

    for(int i = 1; i <= n; ++i)
    {
        visited[i] = false;
    }
    while(stiva.empty() == false)
    {
        int node = stiva.top();
        if(visited[node] == false)
        {
            culoare++;
            DFS2(node, visited, parinti);
        }
        stiva.pop();
    }
    fout << culoare << endl;
    for(int i = 1; i <= culoare; ++i)
    {
        for (int j = 0; j < rezultat[i].size(); ++j)
            fout << rezultat[i][j] << " ";
        fout << endl;
    }

    return 0;
}