Cod sursa(job #2343640)

Utilizator BurlacuMateiBurlacu Matei BurlacuMatei Data 14 februarie 2019 10:10:38
Problema Componente tare conexe Scor 94
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#include <fstream>
#include <vector>
#define MAX 100100

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

struct plusminus{
    bool plus, minus, p;
}uz[MAX];

vector <int> d[MAX];
vector <int> dintors[MAX];
vector <int> ctc[MAX];
int s[MAX];
int n, m, x, y, c, vf;

void parcurgplus(int k);
void parcurgminus(int k);

int main()
{int i, j;

    fin >> n >> m;
    for(i=1;i<=m;i++)
    {
        fin >> x >> y;
        d[x].push_back(y);
        dintors[y].push_back(x);
    }


    for(i=1; i<=n; i++)
        if(!uz[i].plus)
            parcurgplus(i);
    //for(i=1;i<=n;i++)
        //fout << s[i] << ' ';
    for(i=vf;i>=1;i--)
    {
        if(!uz[s[i]].minus)
        {
            c++;
            parcurgminus(s[i]);
            ctc[c].push_back(s[i]);
        }
        else
        {
            ctc[c].push_back(s[i]);
        }

    }

    fout << c << '\n';
    for(i=1;i<=c;i++)
        {for(j=0;j<ctc[i].size();j++)
           fout << ctc[i][j] << ' ';
        fout << '\n';}
    return 0;
}

void parcurgplus(int k)
{int i;

    uz[k].plus = true;
    for(i=0;i<d[k].size();i++)
        if(!uz[d[k][i]].plus)
        parcurgplus(d[k][i]);

    vf++;
    s[vf] = k;

}

void parcurgminus(int k)
{int i;

    uz[k].minus = true;
    for(i=0;i<dintors[k].size();i++)
        if(!uz[dintors[k][i]].minus)
        parcurgminus(dintors[k][i]);

}