Cod sursa(job #2237016)

Utilizator BiancaMariaVulsanVulsan Bianca Maria BiancaMariaVulsan Data 31 august 2018 13:01:54
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#define nmax 100003
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int n,m, viz[nmax], nrc;
vector <int> v[nmax], vt[nmax], a[nmax];
stack <int> s;
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]);
    s.push(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);

    while(!s.empty())
        {if(viz[s.top()])
        {
        conext(s.top());
        nrc++;
        } s.pop();}

    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;
}