Cod sursa(job #2312101)

Utilizator rexlcdTenea Mihai rexlcd Data 4 ianuarie 2019 11:05:34
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <deque>

using namespace std;

vector < int > v[100002],vt[100002];
bool mark[100002];
deque < int > l;

void dfs(int node)
{
    if(mark[node])
        return;
    mark[node]=1;
    for(int i=0;i<v[node].size();i++)
    {
        dfs(v[node][i]);
    }
    l.push_front(node);
}

void dfs_assign(int node, int root)
{
    if(mark[node])
        return;
    mark[node]=1;
    v[root].push_back(node);
    for(int i=0;i<vt[node].size();i++)
    {
        dfs_assign(vt[node][i],root);
    }
}

int main()
{
    ifstream f("ctc.in");
    ofstream g("ctc.out");
    int n,m; f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y; f>>x>>y;
        v[x].push_back(y);
        vt[y].push_back(x);
    }
    for(int i=1;i<=n;i++)
    {
        dfs(i);
    }

    memset(mark,0,sizeof(mark));

    for(int i=1;i<=n;i++)
        v[i].clear();

    int nr=0;
    for(auto node: l)
    {
        dfs_assign(node,node);
    }

    for(int i=1;i<=n;i++)
        if(v[i].size())
            nr++;
    g<<nr<<'\n';
    for(int i=1;i<=n;i++)
        if(v[i].size())
        {
            for(int j=0;j<v[i].size();j++)
                g<<v[i][j]<<" ";
            g<<'\n';
        }

    return 0;
}