Cod sursa(job #1839003)

Utilizator Robert_VRVRobert Vadastreanu Robert_VRV Data 2 ianuarie 2017 11:49:38
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.99 kb
#include <fstream>

using namespace std;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");

struct nod
{
    int inf;
    nod *urm;
};
nod *p[100001], *u[100001], *x[100001], *y[100001];
int n, m, nr, s[100001], pred[100001];

void cit()
{
    int i, j, k;
    fin >> n >> m;
    nod *q;
    for (k=1; k<=m; k++)
    {
        fin >> i >> j;
        if (p[i] == 0)
        {
            q = new nod;
            q->inf = j;
            q->urm = 0;
            p[i] = q;
            u[i] = q;
        }
        else
        {
            q = new nod;
            q->inf = j;
            q->urm = 0;
            u[i]->urm = q;
            u[i] = q;
        }
        if (x[j] == 0)
        {
            q = new nod;
            q->inf = i;
            q->urm = 0;
            x[j] = q;
            y[j] = q;
        }
        else
        {
            q = new nod;
            q->inf = i;
            q->urm = 0;
            y[j]->urm = q;
            y[j] = q;
        }
    }
}
void adancimes(int k)
{
    nod *q;
    s[k] = nr;
    q = new nod;
    q = p[k];
    while (q != 0)
    {
        if (s[q->inf] == 0)
            adancimes(q->inf);
        q = q->urm;
    }
}
void adancimep(int k)
{
    nod *q;
    pred[k] = nr;
    q = new nod;
    q = x[k];
    while (q != 0)
    {
        if (pred[q->inf] == 0)
            adancimep(q->inf);
        q = q->urm;
    }
}
int main()
{
    cit();
    int i, j;
    for (i=1; i<=n; i++)
    {
        if (s[i] == 0)
        {
            nr++;
            adancimes(i);
            adancimep(i);
            for (j=1; j<=n; j++)
                if (s[j] == 0 || pred[j] == 0)
                {
                    s[j] = 0;
                    pred[j] = 0;
                }
        }
    }
    fout << nr << '\n';
    for (i=1; i<=nr; i++){
        for (j=1; j<=n; j++)
            if (s[j] == i)
                fout << j <<" ";
        fout << '\n';
    }
    return 0;
}