Cod sursa(job #1447602)

Utilizator relu.draganDragan Relu relu.dragan Data 4 iunie 2015 20:29:30
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.58 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
void DFSP(vector<vector<int> >& g, stack<int>& s, vector<int>& visited, int n)
{
    visited[n] = 1;
    int i;
    for (i = 0; i < g[n].size(); i++)
    {
        if (visited[g[n][i]] == 0){
            DFSP(g,s,visited,g[n][i]);
        }
    }
    s.push(n);
    printf("%d ", n);
}
void DFSM(vector<vector<int> >& gt, stack<int>& s, vector<int>& visited, vector<int>& where, int n, int which)
{
    where[n] = which;
    int i;
    for (i = 0; i < gt[n].size(); i++){
        if (where[gt[n][i]] == -1){
            DFSM(gt,s,visited,where,gt[n][i],which);
        }
    }
}
int main()
{
    ifstream f("ctc.in");
    ofstream g("ctc.out");
    int N, M, a, b, k = 0,i,j;
    f >> N >> M;

    vector<vector<int> > G(N+1), GT(N+1), result(N+1);
    vector<int> visited(N+1, 0), where(N+1,-1);
    stack<int> s;
    for (i = 0; i < M; i++){
        f >> a >> b;
        G[a].push_back(b);
        GT[b].push_back(a);
    }
    for (i = 1; i <= N; i++){
        if (visited[i] == 0)
            DFSP(G, s, visited, i);
    }
    int count = 0, leader;
    while (!s.empty()){
        leader = s.top();
        if (where[leader] == -1){
            count++;
            DFSM(GT,s,visited,where,leader,count);
        }
        s.pop();
    }
    g << count << endl;
    for (i = 1; i <= N; i++)
        result[where[i]].push_back(i);
    for (i = 1; i <= count; i++){
        for (j = 0; j < result[i].size(); j++)
            g << result[i][j] << " ";
        g << endl;
    }
    f.close();
    g.close();

    return 0;
}