Cod sursa(job #1733289)

Utilizator SolcanMihaiSolcan Mihai Andrei SolcanMihai Data 24 iulie 2016 13:12:46
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.8 kb
#include <cstdio>
#include <vector>
#include <stack>
#include <utility>
#include <bitset>

using namespace std;

int n, m;
vector<int> vecini[100100];
vector<int> vecinix[100100];
bitset<100100> viz;
bitset<100100> vizx;
int nr = 0;

vector<vector<int> > componente;

stack<int> st;

void citire()
{
    scanf("%d %d", &n, &m);

    int tmp1, tmp2;

    for(int i = 0; i < m; i++)
    {
        scanf("%d %d", &tmp1, &tmp2);
        tmp1--;
        tmp2--;

        vecini[tmp1].push_back(tmp2);
        vecinix[tmp2].push_back(tmp1);
    }
}

void dfs(int x)
{
    int l = vecini[x].size();
    viz[x] = true;

    for(int i = 0; i < l; i++)
    {
        if(viz[vecini[x][i]] == false)
        {
             dfs(vecini[x][i]);
        }
    }
    st.push(x);
}

void dfsx(int x)
{
    componente[nr].push_back(x);
    int l = vecinix[x].size();
    vizx[x] = true;

    for(int i = 0; i < l; i++)
    {
        if(vizx[vecinix[x][i]] == false)
        {
            dfsx(vecinix[x][i]);
        }
    }
}

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

    while(!st.empty())
    {
        int x = st.top();
        st.pop();

        if(vizx[x] == false)
        {
            componente.push_back(vector<int>());
            dfsx(x);
            nr++;
        }
    }
}

void afisare()
{
    printf("%d\n", nr);

    for(int i = 0; i < nr; i++)
    {
        for(int j = 0; j < componente[i].size(); j++)
        {
            printf("%d ", componente[i][j] + 1);
        }
        printf("\n");
    }
}

int main()
{
    freopen("ctc.in", "r", stdin);
    freopen("ctc.out", "w", stdout);

    citire();
    ctc();
    afisare();


    return 0;
}