Cod sursa(job #2236983)

Utilizator BiancaMariaVulsanVulsan Bianca Maria BiancaMariaVulsan Data 31 august 2018 11:26:11
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
#include <iostream>
#include <fstream>
#include <vector>
#define nmax 100003
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int n,m, viz1[nmax], viz2[nmax], viz[nmax], fr[nmax];
vector <int> v[nmax], vt[nmax], a[nmax];

void citire()
{
    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);
    }
}

void conex(int start, int sign)
{
    int j;
    if(sign==1)
         viz1[start]=1;
    else
         viz2[start]=1;
    viz[start]=1;
    for(j=0; j<v[start].size(); j++)
        if(!viz[v[start][j]])
        {
            conex(v[start][j], sign);
        }
}

void conext(int start, int sign)
{
    int j;
    if(sign==1)
         viz1[start]=1;
    else
         viz2[start]=1;
    viz[start]=1;
    for(j=0; j<vt[start].size(); j++)
        if(!viz[vt[start][j]])
        {
            conext(vt[start][j], sign);
        }
}

int main()
{
    int i,j, nr=0;
    citire();
    for(i=1; i<=n; i++)
    if(!fr[i])
    {
        for(j=1; j<=n; j++)
            {viz[j]=0; viz1[j]=0;}
        conex(i, 1);

        for(j=1; j<=n; j++)
            {viz[j]=0; viz2[j]=0;}
        conext(i, 0);

        for(j=1; j<=n; j++)
            if(viz1[j] && viz2[j])
            {
                a[nr].push_back(j); fr[j]=1;
            }
        nr++;
    }
    g<<nr<<endl;
    for(i=0; i<nr; i++)
        {for(j=0; j<a[i].size(); j++)
        g<<a[i][j]<<" ";
    g<<endl;}
    f.close();
    g.close();
    return 0;
}