Cod sursa(job #2671984)

Utilizator VarothexVartic Mihai-Vlad Varothex Data 12 noiembrie 2020 21:45:14
Problema Componente tare conexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.38 kb
#include <iostream>
#include <fstream>
#define Nmax 100000

using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");

long n, m, k, nr, t[Nmax], viz[Nmax];

struct elem
{
    long inf;
	elem *urm;
}*a[Nmax], *at[Nmax], *sol[Nmax];

void p1(long x)
{
    for (elem *p = a[x]; p; p=p->urm)
        if (viz[p->inf]==0)
        {
            viz[p->inf] = 1;
            p1(p->inf);
        }
    k++;
    t[k]=x;
}

void p2(long x, long nr)
{
	elem *q = new elem;
	q->inf = x;
	q->urm = sol[nr];
	sol[nr] = q;
	viz[x] = -1;
	for(elem *p=at[x];p;p=p->urm)
        if(viz[p->inf] == 1)
            p2(p->inf, nr);
}

int main()
{
    long x, y;
    f >> n >> m;
    for (long i = 0; i < m; i++)
    {
        f >> x >> y;
        elem *p = new elem;
        p->inf = y;
        p->urm = a[x];
        a[x] = p;
        p = new elem;
        p->inf = x;
        p->urm = at[y];
        at[y] = p;
    }
    long i;
    for (i = 1;i <= n;i++)
        if (!viz[i])
        {
            viz[i] = 1;
            p1(i);
        }
    for (i = n; i >= 1; i--)
	if (viz[t[i]] == 1)
	{
		nr++;
		p2(t[i],nr);
	}

    g << nr << '\n';
    for (long i = 1; i <= nr; i++)
    {
        while(sol[i])
        {
            g << sol[i]->inf << " ";
            sol[i] = sol[i]->urm;
        }
        g << '\n';
    }

    return 0;
}