Cod sursa(job #2416411)

Utilizator GoogalAbabei Daniel Googal Data 27 aprilie 2019 15:24:26
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.67 kb
#include <algorithm>
#include <iostream>
#include <fstream>
#include <bitset>
#include <vector>
#include <stack>

using namespace std;

ifstream in("ctc.in");
ofstream out("ctc.out");

const int NMAX = 1e5;

int n, m, no;

vector < int > gi[1 + NMAX];
vector < int > g[1 + NMAX];
vector < int > ctc[1 + NMAX];

bitset < 1 + NMAX > vis;
stack < int > st;

bool cmp(vector < int > &a, vector < int > &b)
{
    return a[0] < b[0];
}

void dfs1(int node)
{
    vis[node] = 1;
    for(int i = 0; i < g[node].size(); i++)
    {
        int to = g[node][i];
        if(vis[to] == 0)
            dfs1(to);
    }
    st.push(node);
}

void dfs2(int node)
{
    vis[node] = 1;
    for(int i = 0; i < gi[node].size(); i++)
    {
        int to = gi[node][i];
        if(vis[to] == 0)
            dfs2(to);
    }
    ctc[no].push_back(node);
}

int main()
{
    in >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int x, y;
        in >> x >> y;
        g[x].push_back(y);
        gi[y].push_back(x);
    }

    for(int i = 1; i <= n; i++)
        if(vis[i] == 0)
            dfs1(i);

    vis = 0;

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

        st.pop();

        if(vis[node] == 0)
        {
            no++;
            dfs2(node);
        }
    }

    for(int i = 1; i <= no; i++)
        sort(ctc[i].begin(), ctc[i].end());

    sort(ctc + 1, ctc + no + 1, cmp);

    out << no << '\n';

    for(int i = 1; i <= no; i++)
    {
        for(int j = 0; j < ctc[i].size(); j++)
            out << ctc[i][j] << ' ';

        out << '\n';
    }

    in.close();
    out.close();

    return 0;
}