Cod sursa(job #396638)

Utilizator cristiprgPrigoana Cristian cristiprg Data 15 februarie 2010 17:54:44
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.72 kb
#include <cstdio>
#include <stack>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
#define DIM 100005

struct nod
{
    int x;
    bool exista;
    nod *next;
};

nod *G[DIM], *Gt[DIM];
int n, m, v[DIM];
stack<int> S;
//set<int> SET[DIM];
vector<int> V[DIM];


void addMuchie(int i, int j, nod *G[])
{
    nod *p = new nod;
    p->x = j;
    p->next = G[i];
    G[i] = p;
}

void DFS(int i)
{
    v[i] = 1;
    for (nod *p = G[i]; p; p = p -> next)
        if (!v[p->x])
                DFS(p->x);
    S.push(i);
}

void DFS2(int i, int count)
{
    v[i] = 1;
//    SET[count].insert(i);
    V[count].push_back(i);
    for (nod *p = Gt[i]; p; p = p -> next)
        if (!v[p->x])
                DFS2(p->x, count);
}

    int Count = 0;

void Korasaju()
{
    for (int i = 1; i <= n; ++i)
        if (!v[i])
            DFS(i);
    
    for (int i = 1; i <= n; ++i)
        v[i] = 0;

    for (; S.size(); S.pop())
    {
        int x = S.top();
        if (!v[x])
                DFS2(x, ++Count);
        
            
    }
}

int main()
{
    FILE *f = fopen("ctc.in", "r");
    fscanf(f, "%d%d", &n, &m);
    for (int x, y;m;--m)
    {
        fscanf(f, "%d%d", &x, &y);
        addMuchie(x, y, G);
        addMuchie(y, x, Gt);
    }
    
    Korasaju();
    f = fopen("ctc.out", "w");
    fprintf(f, "%d\n", Count);
 // sort(SET+1, SET+Count+1);
    for (int i = 1; i <= Count; ++i)
    {
   //     fprintf(f, "%d ",V[i].size());
        for (vector<int>::iterator it = V[i].begin(); it != V[i].end(); ++it)
                fprintf(f, "%d ", *it);
        fprintf(f, "\n");
    }    
    
    
    fclose(f);
    return 0;
}