Cod sursa(job #2202056)

Utilizator petrut22Petrut petrut22 Data 7 mai 2018 13:13:36
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <iostream>
#include <fstream>
//Roy - Warshall
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
bool D[101][101];
int n, m,c[101];

void citire()
{
    int x, y;
    f >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        f >> x >> y;
        D[x][y] = 1;
    }
}

void Roy_Warshall()
{
    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                D[i][j] = D[i][j] || (D[i][k] && D[k][j]);
}

int nr_comp_tare_conexe()
{
    int  nrc = 0;
    for(int i = 1; i <= n; i++)
        c[i] = 0;
    for(int i = 1; i <= n; i++)
        if(c[i] == 0)
        {
            c[i] = ++nrc;
            for(int j = 1; j <= n; j++)
                if(c[j] == 0 && D[i][j] == 1 && D[j][i] == 1)
                    c[j] = nrc;
        }
    return nrc;
}

int main()
{
    int nrc;
    citire();
    Roy_Warshall();
    nrc=nr_comp_tare_conexe();
    g << nrc <<endl;
    for(int i = 1; i <= nrc; i++)
    {
        for(int j = 1; j <= n; j++)
            if(c[j] == i)
                g << j << ' ';
        g << endl;
    }
    return 0;
}