Cod sursa(job #2204529)

Utilizator TudoseSanzianaTudose Sanziana TudoseSanziana Data 16 mai 2018 11:47:13
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.96 kb
#include <bits/stdc++.h>
using namespace std;

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

const int N_MAX = 1e5;

int n, m;
vector<int> gr[N_MAX + 2], grt[N_MAX + 2];

int num;
int ord[2][N_MAX + 2];
bool vis[N_MAX + 2];

int daddy[N_MAX + 2], depth[N_MAX + 2];
int find(int node);
void join(int r1, int r2);

vector<int> ans[N_MAX + 2];

void dfs1(int node)
{
    vis[node] = true;

    for(auto it: gr[node])
        if(!vis[it])
            dfs1(it);

    num++;
    ord[0][node] = num;
    ord[1][num] = node;
}

void dfs2(int node)
{
    vis[node] = true;

    for(auto it: grt[node])
        if(!vis[it])
        {
            if(ord[0][daddy[node]] > ord[0][daddy[it]])
                join(find(it), find(node));

            dfs2(it);
        }
}

int main()
{
    in >> n >> m;
    while(m--)
    {
        int x, y;
        in >> x >> y;
        gr[x].push_back(y);
        grt[y].push_back(x);
    }

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

    for(int i = 1; i <= n; i++)
    {
        vis[i] = 0;
        daddy[i] = i;
        depth[i] = 1;
    }

    for(int i = n; i >= 1; i--)
        if(!vis[ord[1][i]])
            dfs2(ord[1][i]);

    int nr = 0;
    for(int i = 1; i <= n; i++)
    {
        int val = find(i);
        ans[val].push_back(i);

        if(ans[val].size() == 1)
            nr++;
    }

    out << nr << '\n';
    for(int i = 1; i <= n; i++)
        if(ans[i].size())
        {
            for(auto it: ans[i])
                out << it << ' ';
            out << '\n';
        }

    return 0;
}

int find(int node)
{
    int r = daddy[node];
    while(daddy[r] != r)
        r = daddy[r];

    return r;
}

void join(int r1, int r2)
{
    if(depth[r1] == depth[r2])
    {
        daddy[r1] = r2;
        depth[r2]++;
    }
    else if(depth[r1] > depth[r2])
        daddy[r2] = r1;
    else
        daddy[r1] = r2;
}