Cod sursa(job #1740724)

Utilizator tudorgalatanRoman Tudor tudorgalatan Data 12 august 2016 10:49:27
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <fstream>
#include <vector>

using namespace std;

void DFS (unsigned int node);

unsigned int N, M;
unsigned int x, y;

vector <unsigned int> G[10001];
unsigned int matrix[10001][10001];
bool used[10001];
unsigned int i, j, k;

unsigned int sol;

int main ()
{
    ifstream fin ("ctc.in");
    fin >> N >> M;
    for (i=1; i<=M; i++)
    {
        fin >> x >> y;
        matrix[x][y] = 1;
    }
    fin.close();
    for (k=1; k<=N; k++)
        for (i=1; i<=N; i++)
            for (j=1; j<=N; j++)
                if (i!=j && matrix[i][k]!=0 && matrix[k][j]!=0 && (matrix[i][j]>matrix[i][k]+matrix[k][j] || matrix[i][j]==0))
                    matrix[i][j] = matrix[i][k] + matrix[k][j];
    for (i=1; i<=N; i++)
        for (j=1; j<=N; j++)
            if (matrix[i][j] > 0)
                matrix[i][j] = 1;
    for (i=1; i<=N; i++)
        for (j=1; j<=N; j++)
            if (matrix[i][j] == 1)
            {
                G[i].push_back(j);
                G[j].push_back(i);
            }
    for (i=1; i<=N; i++)
        if (!used[i])
        {
            DFS(i);
            sol++;
        }
    ofstream fout ("ctc.out");
    fout << sol+1;
    fout.close();
    return 0;
}

void DFS (unsigned int node)
{
    vector <unsigned int> :: iterator i;
    used[node] = 1;
    for (i=G[node].begin(); i!=G[node].end(); i++)
        if (!used[*i])
            DFS(*i);
}