Cod sursa(job #1250462)

Utilizator malina_floreaMalina Florea malina_florea Data 28 octombrie 2014 10:08:59
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <fstream>
#define DMAX 100
using namespace std;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");

void citire();
void ctc();
void BFS(int, bool[DMAX][DMAX], int[DMAX]);
void init();
void afisare();

bool G[DMAX][DMAX], GT[DMAX][DMAX];
bool use[DMAX];
int n, m;

int ok[DMAX];
int c[DMAX];
int sol1[DMAX], sol2[DMAX];

int main()
{
    citire();
    ctc();
    
    fin.close();
    fout.close();
    return 0;
}

void citire()
{
    int i, a, b;
        
    fin>> n>> m;
    for (i=1; i<=m; i++)
    {
        fin>> a>> b;
        G[a][b]=true;
        GT[b][a]=true;
    }
}

void ctc()
{
    int i;
    for (i=1; i<=n; i++)
        if (!use[i])
        {
            init();
            BFS(i, G, sol1);
            BFS(i, GT, sol2);
            afisare();
        }
}

void init()
{
    sol1[0]=0, sol2[0]=0;
}

void BFS (int start, bool graf[DMAX][DMAX], int sol[DMAX])
{
    int prim, ultim;
    int p, i;
    
    sol[0]=0;
    
    c[1]=start; use[start]=1;
    prim=ultim=1;
    
    while (prim<=ultim)
    {
        p=c[prim++];
        sol[++sol[0]]=p;
        
        for (i=1; i<=n; i++)
            if (!use[i])
            {
                use[i]=true;
                c[++ultim]=i;
            }
    }
}

void afisare()
{
    int i;
    
    for (i=1; i<=n; i++)
        if (ok[i]==2)
            fout<< i<< ' ';
        else
            use[i]=false;
    fout<< '\n';
}