Cod sursa(job #1889208)

Utilizator SolcanMihaiSolcan Mihai Andrei SolcanMihai Data 22 februarie 2017 17:04:15
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.84 kb
#include <cstdio>
#include <vector>
#include <stack>


using namespace std;

int n, m;
int viz[100005];
int vizx[100005];
vector<int> vecini[100005];
vector<int> vecinix[100005];
stack<int> st;
vector<int> solutie;
vector<vector<int> > solsol;

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

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

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

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

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

    st.push(x);
}

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

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

    solutie.push_back(x);
}

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

    solutie.clear();

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

        if(vizx[x] == false)
        {
            solutie.clear();
            dfsx(x);
            solsol.push_back(solutie);
        }
    }
}

void afisare()
{
    printf("%d\n", solsol.size());

    int l = solsol.size();

    for(int i = 0; i < l; i++)
    {
        int ll = solsol[i].size();

        for(int j = 0; j < ll; j++)
        {
            printf("%d ", solsol[i][j] + 1);
        }

        printf("\n");
    }
}

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

    citire();
    solve();
    afisare();

    return 0;
}