Cod sursa(job #2224845)

Utilizator stanbianca611Stan Bianca stanbianca611 Data 25 iulie 2018 12:49:25
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
ifstream f ("ctc.in");
ofstream g ("ctc.out");
vector <int> a[100005], atrans[100005];
int viz[100005], postordine[100005], nr, n, m, nrc, ok;
void DFS(int x)
{
    int i;
    viz[x]=1;
    for(i=0; i<a[x].size(); i++)
    {
        if(!viz[a[x][i]])
            DFS(a[x][i]);
    }
    postordine[++nr]=x;
}
void DFST(int x)
{
    int i;
    viz[x]=0;
    if(ok)g<<x<<" ";
    for(i=0; i<atrans[x].size(); i++)
    {
        if(viz[atrans[x][i]])
            DFST(atrans[x][i]);
    }
}


int main()
{
    int i, x, y, j;
    f>>n>>m;
    for(i=1; i<=m; i++)
    {
        f>>x>>y;
        a[x].push_back(y);
        atrans[y].push_back(x);
    }
    for(i=1; i<=n; i++)
        sort(a[i].begin(), a[i].end());
    for(i=1; i<=n; i++)
    {
        if(!viz[i])
            DFS(i);
    }
    for(i=n; i>=1; i--)
    {
        if(viz[postordine[i]])
        {
            nrc++;
            DFST(postordine[i]);
        }
    }
    g<<nrc;
    memset(viz, 1, sizeof(viz));
    ok=1;
    for(i=n; i>=1; i--)
    {
        if(viz[postordine[i]])
        {
            g<<"\n";
            DFST(postordine[i]);
        }
    }
    return 0;
}