Cod sursa(job #2281504)

Utilizator crion1999Anitei cristi crion1999 Data 12 noiembrie 2018 13:23:14
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 kb
#include <bits/stdc++.h>
#define NMAX 100010
using namespace std;
ifstream fi("ctc.in");
ofstream fo("ctc.out");
vector<int> graph[NMAX];
vector<int> transposed[NMAX];
vector<int> components[NMAX];
stack<int> stacc;
bool visited[NMAX];
int N, M;

void DFS(int vertex)
{
    if(visited[vertex])
        return;

    visited[vertex] = 1;
    for(auto y:graph[vertex])
    {
        DFS(y);
    }
    stacc.push(vertex);
}

void DFSP(int vertex, int paint)
{
    if(visited[vertex])
        return;

    visited[vertex] = 1;
    components[paint].push_back(vertex);
    for(auto y:transposed[vertex])
    {
        DFSP(y,paint);
    }
}


int main()
{
    int a,b;
    fi>>N>>M;
    for(int i = 1; i <= M; ++i)
    {
        fi>>a>>b;
        graph[a].push_back(b);
        transposed[b].push_back(a);
    }
    for(int i = 1; i <= N; ++i)
    {
        DFS(i);
    }
    memset(visited, 0, N+10);
    int d = 0;
    for(;!stacc.empty();)
    {
        int tp = stacc.top();
        stacc.pop();
        DFSP(tp,++d);
    }
    int k = 0;
    for(int i = 1; i <= d; ++i)
    {
        if(components[i].size() > 0)
            k++;
    }
    fo<<k<<"\n";
    for(int i = 1; i <= d; ++i)
    {
        if(components[i].size() > 0)
        {
            for(int j = 0; j < components[i].size(); ++j)
                fo<<components[i][j]<<" ";
            fo<<"\n";
        }
    }
}