Cod sursa(job #1376438)

Utilizator lacraruraduRadu Matei Lacraru lacraruradu Data 5 martie 2015 17:25:02
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include <fstream>

#define N 100001
#define M 200001
using namespace std;

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

int n, m;
int ctc = 0;

int lst[N], vf[2 * M], urm[2 * M], nvf = 0;
bool intoarcere[2 * M];

bool ok1[N];
int ord[N], nord = 0;

bool ok2[N];
int rez[2 * N], nrez = 0;

void df_1(int x)
{
    ok1[x] = 1;

    for(int i = lst[x]; i; i = urm[i])
            if(!intoarcere[i] && !ok1[vf[i]])
                df_1(vf[i]);

    ord[++nord] = x;
}

void df_2(int x)
{
    ok2[x] = 1;
    rez[++nrez] = x;

    for(int i = lst[x]; i; i = urm[i])
        if(intoarcere[i] && !ok2[vf[i]])
            df_2(vf[i]);
}

int main()
{
    in >> n >> m;

    for(int i = 1; i <= m; i++)
    {
        int x, y;
        in >> x >> y;

        vf[++nvf] = y;
        urm[nvf] = lst[x];
        lst[x] = nvf;
        vf[++nvf] = x;
        intoarcere[nvf] = 1;
        urm[nvf] = lst[y];
        lst[y] = nvf;
    }

    for(int i = 1; i <= n; i++)
        if(!ok1[i])
            df_1(i);

    for(int i = n; i >= 1; i--)
        if(!ok2[ord[i]])
        {
            df_2(ord[i]);
            rez[++nrez] = -1;
            ctc++;
        }

    out << ctc << '\n';

    for(int i = 1; i <= nrez; i++)
        if(rez[i] != -1)
            out << rez[i] << ' ';
        else
            out << '\n';
    return 0;
}