Cod sursa(job #1889275)

Utilizator gabor.vlad13lil pump gabor.vlad13 Data 22 februarie 2017 17:37:02
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.53 kb
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#define NMAX 100005

using namespace std;

vector<int> GR[NMAX];
vector<int> IV[NMAX];
vector<int> solc[NMAX];
stack<int> st;
int viz[NMAX];
int nrTot=1, n, m;

void afisare()
{
    cout<<nrTot-1<<"\n";
    for (int i=1; i<nrTot; i++)
    {
        vector<int>::iterator it;
        for(it = solc[i].begin(); it!=solc[i].end(); it++)
            cout<<*it<<" ";
        cout<<"\n";
    }
}
void dfs2(int x, int c)
{
    vector<int>:: iterator it;
    viz[x] = 1;
    for (it = IV[x].begin(); it!=IV[x].end(); it++)
    {
        if (!viz[*it])
            dfs2(*it, c);
    }
    solc[c].push_back(x);
}
void dfs(int x)
{
    vector<int>::iterator it;
    viz[x] = 1;
    for (it=GR[x].begin(); it!=GR[x].end(); it++)
    {
        if (viz[*it] == 0)
            dfs(*it);
    }

    st.push(x);
}


void solve()
{
    for (int i=1; i<=n; i++)
    {
        if (!viz[i])
            dfs(i);
    }
    memset(viz, NULL, sizeof(viz));
    while(!st.empty())
    {
        int x = st.top();
        //viz[x] = 1;
        st.pop();
        if (!viz[x])
        {
            dfs2(x, nrTot);
            nrTot++;
        }
    }
}
void read()
{
    scanf("%d %d\n", &n, &m);
    int x, y;
    for (int i=1; i<=m; i++)
    {
        scanf("%d %d\n", &x, &y);
        GR[x].push_back(y);
        IV[y].push_back(x);
    }
}

int main()
{
    freopen("ctc.in", "r", stdin);
    freopen("ctc.out", "w", stdout);
    read();
    solve();
    afisare();
    return 0;
}