Cod sursa(job #2165907)

Utilizator UrsuDanUrsu Dan UrsuDan Data 13 martie 2018 14:22:51
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <cstdio>
#include <vector>
#include <stack>

using namespace std;

const int N_MAX = 100000;

vector <int> g[N_MAX + 1], gt[N_MAX + 1], answer[N_MAX + 1];
stack <int> st;

bool vis[N_MAX + 1];
int ctc[N_MAX + 1];

void dfs(int node)
{
    vis[node] = true;
    for(int son : g[node])
        if(vis[son] == false)
            dfs(son);
    st.push(node);
}

void dfst(int node, int nr)
{
    ctc[node] = nr;
    for(int son : gt[node])
        if(ctc[son] == 0)
            dfst(son, nr);
}

int main()
{
    freopen("ctc.in", "r", stdin);
    freopen("ctc.out", "w", stdout);
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        g[x].push_back(y);
        gt[y].push_back(x);
    }
    for(int i = 1; i <= n; i++)
        if(vis[i] == false)
            dfs(i);
    int nr = 0;
    while(st.empty() == false)
    {
        int node = st.top();
        st.pop();
        if(ctc[node] == 0)
        {
            nr++;
            dfst(node, nr);
        }
    }
    for(int i = 1; i <= n; i++)
        answer[ctc[i]].push_back(i);
    printf("%d\n", nr);
    for(int i = 1; i <= nr; i++)
    {
        for(int node : answer[i])
            printf("%d ", node);
        printf("\n");
    }
    return 0;
}