Cod sursa(job #1430358)

Utilizator sing_exFMIGhita Tudor sing_ex Data 8 mai 2015 11:42:54
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>

using namespace std;

int n,**m,*v;
stack<int> s;
vector<int> *a;

void dfs(int x) {
    v[x] = 1;
    int i;
    for (i=1;i<=n;i++) {
        if (!v[i] && m[x][i] == 1) {
            dfs(i);
        }
    }
    s.push(x);
}

int main()
{
    int i,j,x,y,c = 0;
    ifstream f("ctc.in");
    f>>n>>i;
    v = new int[n+1];
    a = new vector<int>[n+1];
    for (i=1;i<=n;i++) v[i] = 0;
    m = new int*[n+1];
    for (i=1;i<=n;i++) m[i] = new int[n+1];
    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++) m[i][j] = 0;
    while (f>>x>>y) m[x][y] = 1;
    f.close();
    for (i=1;i<=n;i++)
        if (!v[i]) dfs(i);
    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++)
            if (m[i][j] == 1 && m[j][i] == 0) {
                m[i][j]++;
                m[j][i] = 1;
            }
    for (i=1;i<=n;i++) v[i] = 0;
    stack<int> s1 = stack<int>(s);
    while (!s1.empty()) {
        while (!s.empty()) s.pop();
        x = s1.top();
        s1.pop();
        if (v[x]) continue;
        dfs(x);
        while (!s.empty()) {
            a[c].push_back(s.top());
            s.pop();
        }
        c++;
    }
    ofstream g("ctc.out");
    g<<c;
    g<<endl;
    for (i=0;i<c;i++) {
        for (j=0;(unsigned)j<a[i].size();j++)
            g<<a[i][j]<<" ";
        g<<endl;
    }
    g.close();
    return 0;
}