Cod sursa(job #2207730)

Utilizator BiancaMariaVulsanVulsan Bianca Maria BiancaMariaVulsan Data 26 mai 2018 15:59:35
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.66 kb
//Dându-se un graf orientat G = (V, E) se cere să se determine componentele sale tare conexe.
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int n,M, viz[100001], viz1[100001], nr;
int p[100001], m[100001];
vector <int> v[100001], vt[100001], a[100001];

void citire()
{
    int i,j,k;
    f>>n>>M;
    for(k=0; k<M; k++)
    {
        f>>i>>j;
        v[i].push_back(j);
        vt[j].push_back(i);
    }
}

void parcAdancimev(int i, int sign)
{
    int j;
    if(sign==1)
        p[i]=1;
    else
        m[i]=1;
    viz1[i]=1;
    for(j=0; j<v[i].size(); j++)
        if(viz1[v[i][j]]==0)
        {viz1[v[i][j]]=1; parcAdancimev(v[i][j], sign);}
}
void parcAdancimevt(int i, int sign)
{
    int j;
    if(sign==1)
        p[i]=1;
    else
        m[i]=1;
    viz1[i]=1;
    for(j=0; j<vt[i].size(); j++)
        if(viz1[vt[i][j]]==0)
        {viz1[vt[i][j]]=1; parcAdancimevt(vt[i][j], sign);}
}

void algPlusMinus()
{
    int i,j;
    for(i=1; i<=n; i++)
    {
        if(viz[i]==0)
            nr++;
        for(j=1; j<=n; j++)
                {viz1[j]=0; p[j]=0;}
        parcAdancimev(i, 1);
        for(j=1; j<=n; j++)
                {viz1[j]=0; m[j]=0;}
        parcAdancimevt(i, 0);

        for(j=1; j<=n; j++)
            if(p[j] && m[j] && viz[j]==0)
            {a[nr].push_back(j); viz[j]=1;}
    }
}

int main()
{
    int i,j;
    citire();
    algPlusMinus();
    g<<nr<<endl;
    for(i=1; i<=nr; i++)
    {for(j=0; j<a[i].size(); j++)
        g<<a[i][j]<<" ";
     g<<endl;}
    f.close();
    g.close();
    return 0;
}