Cod sursa(job #1756147)

Utilizator cojocarugabiReality cojocarugabi Data 11 septembrie 2016 22:35:54
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.76 kb
# include <stdio.h>
# include <bits/stdc++.h>
using namespace std;
# define fi cin
# define fo cout
# define x first
# define y second
# define ll long long
# define IOS ios_base :: sync_with_stdio(0);cin.tie(0)
# define p(v) cerr << #v << " = " << v << '\n'
# define p2(v) cerr << #v << " = " << (complex < int > (v.x,v.y)) << '\n'
# define vi vector < int >
# define vll vector < ll >
# define pii pair < int , int >
# define CF
int main(void)
{
    #ifdef CF
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    #endif // CF;'
    srand(time(0));
    fo << fixed << setprecision(7);
    cerr << fixed << setprecision(7);
    int n,m;
    IOS;
    fi>>n>>m;
    static vi s[1 << 20];
    static vi v[1 << 20];
    while (m --)
    {
        int a,b;
        fi>>a>>b;
        s[a].push_back(b);
        v[b].push_back(a);
    }
    static vi order;
    static int was[1 << 20];
    function < void(int) > dfs1 = [&](int node)
    {
        was[node] = 1;
        for (auto it : s[node])
            if (!was[it])
                dfs1(it);
        order.push_back(node);
    };
    for (int i = 1;i <= n;++i)
        if (!was[i])
            dfs1(i);
    static vi c;
    static vector < vi > ans;
    function < void(int) > dfs2 = [&](int node)
    {
        was[node] = 0;
        c.push_back(node);
        for (auto it : v[node])
            if (was[it])
                dfs2(it);
    };
    reverse(order.begin(),order.end());
    for (auto it : order)
    if (was[it])
    {
        c.clear();
        dfs2(it);
        ans.push_back(c);
    }
    fo << ans.size() << '\n';
    for (auto it : ans)
    {
        for (auto x : it) fo << x << ' ';
        fo << '\n';
    }
    cerr << "Time elapsed :" << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
    return 0;
}