Cod sursa(job #2555379)

Utilizator LazarRazvanLazar Razvan LazarRazvan Data 23 februarie 2020 22:32:34
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.41 kb
#include <cstdio>
#include <iostream>
#include <vector>
#include <stack>

#define NMAX 100001

#define GREEN 0                     //not visited
#define YELLOW 1                    //visited in the first DFS
#define RED 2                       //visited in the second DFS

using namespace std;

int v, e;                           //nr of vertices, nr of edges
int nodeColor[NMAX];                //the color of the node (SEE DEFINITION)
int nrSCC = 0;                      //nr of strongly connected components

vector <int> graph[NMAX];           //adjacency lists
vector <int> graphTransposed[NMAX]; //the adjacency lists for the transposed graph
vector <int> SCC[NMAX];             //the strongly connected components
stack  <int> st;                    //the topological sort of the graph

void read();
void DFS(int);
void DFStranspose(int);
void Kosaraju();
void topologicalSort();
void write();

int main() {

    read();

    Kosaraju();

    write();

    return 0;
}

void read()
{
    freopen("ctc.in", "r", stdin);

    scanf("%d%d", &v , &e);

    int x, y;

    for (int i = 1; i <= e; i++)
    {
        scanf("%d%d", &x, &y);

        graph[x].push_back(y);
        graphTransposed[y].push_back(x);
    }
}

void Kosaraju()
{
    topologicalSort();

    while (!st.empty())
    {
        int node = st.top();
        printf("%d ", node);

        if (nodeColor[node] == YELLOW)
        {
            ++nrSCC;
            DFStranspose(node);
        }
        st.pop();
    }
}

void topologicalSort()
{
    for (int i = 1; i <= v; i++)
    {
        if (nodeColor[i] == GREEN)
            DFS(i);
    }
}

void DFS(int node)
{
    nodeColor[node] = YELLOW;

    for (unsigned int i = 0; i < graph[node].size(); i++)
    {
        int neighbour = graph[node][i];

        if (nodeColor[neighbour] == GREEN)
            DFS(neighbour);
    }

    st.push(node);
}

void DFStranspose(int node)
{
    nodeColor[node] = RED;
    SCC[nrSCC].push_back(node);

    for (unsigned int i = 0; i < graphTransposed[node].size(); i++)
    {
        int neighbour = graphTransposed[node][i];

        if (nodeColor[neighbour] == YELLOW) {
            DFStranspose(neighbour);
        }
    }
}

void write()
{
    freopen("ctc.out", "w", stdout);

    printf("%d\n", nrSCC);

    for (int i = 1; i <= nrSCC; i++)
    {
        for (auto j = SCC[i].begin(); j != SCC[i].end(); ++j)
            printf("%d ", *j);
        printf("\n");
    }

    fclose(stdout);
}