Cod sursa(job #2236998)

Utilizator BiancaMariaVulsanVulsan Bianca Maria BiancaMariaVulsan Data 31 august 2018 12:35:57
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <iostream>
#include <fstream>
#include <vector>
#define nmax 100003
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int n,m, viz[nmax], nrc, inv[nmax], nr;
vector <int> v[nmax], vt[nmax], a[nmax];

void conex(int start)
{
    int j;
    viz[start]=1;
    for(j=0; j<v[start].size(); j++)
        if(!viz[v[start][j]])
        {
            conex(v[start][j]);
            inv[++nr]=start;
        }
}

void conext(int start)
{
    int j;
    viz[start]=0;
    a[nrc].push_back(start);
    for(j=0; j<vt[start].size(); j++)
        if(viz[vt[start][j]])
        {
            conext(vt[start][j]);
        }
}

int main()
{
    int i,j,k;
    f>>n>>m;
    for(k=1; k<=m; k++)
    {
        f>>i>>j;
        v[i].push_back(j);
        vt[j].push_back(i);
    }

    for(i=1; i<=n; i++)
        if(!viz[i])
            conex(i);
    for(i=n; i>0; i--)
        if(viz[inv[i]])
    {
        conext(inv[i]);
        nrc++;
    }

    g<<nrc<<endl;
    for(i=0; i<nrc; i++)
        {for(j=0; j<a[i].size(); j++)
        g<<a[i][j]<<" ";
    g<<endl;}
    f.close();
    g.close();
    return 0;
}