Cod sursa(job #1920154)

Utilizator andrei.sasaAndrei SaSa andrei.sasa Data 9 martie 2017 22:42:31
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

vector <int> G1[100010];
vector <int> G2[100010];
vector <int> C[100010];

struct str
{
    int nod,dist;
}F[100010];

bool myfunction (str i,str j) { return (i.dist>j.dist); }

int viz[100010],viz1[100010],n,m,tp,nrnod;

void DFS1(int x,int comp)
{
    nrnod++;
    F[x].dist=++tp;
    F[x].nod=x;
    viz[x]=comp;
    for(int i=0;i<G1[x].size();i++)
        if(!viz[G1[x][i]]) DFS1(G1[x][i],comp);
}

void DFS2(int x, int comp)
{
    nrnod++;
    C[comp].push_back(x);
    viz1[x]=comp;
    for(int i=0;i<G2[x].size();i++)
        if(!viz1[G2[x][i]]) DFS2(G2[x][i],comp);
}

int main()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int a,b;
        f>>a>>b;
        G1[a].push_back(b);
        G2[b].push_back(a);
    }
    int comp=1;
    DFS1(1,1);
    for(int i=1;i<=n && nrnod<n;i++)
        if(!viz[i]) DFS1(i,++comp);
    sort(F+1,F+n+1,myfunction);
    nrnod=0;
    DFS2(F[1].nod,1);
    comp=1;
    for(int i=1;i<=n && nrnod<n;i++)
        if(!viz1[F[i].nod]) DFS2(F[i].nod,++comp);
    g<<comp<<'\n';
    for(int i=1;i<=comp;i++)
    {
        for(int j=0;j<C[i].size();j++)
            g<<C[i][j]<<' ';
        g<<'\n';
    }

    return 0;
}