Cod sursa(job #2343558)

Utilizator BurlacuMateiBurlacu Matei BurlacuMatei Data 14 februarie 2019 09:12:15
Problema Componente tare conexe Scor 12
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.97 kb
#include <fstream>
#define MAX 6000

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

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

int d[MAX][MAX];
int dintors[MAX][MAX];
int ctc[MAX][MAX];
int n, m, x, y, c;

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

int main()
{int i, j;

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

/*for(i=1;i<=n;i++)
        {for(j=1;j<=d[i][0];j++)
            fout << d[i][j] << ' ';
        fout << '\n';}

    for(i=1;i<=n;i++)
        {for(j=1;j<=dintors[i][0];j++)
            fout << dintors[i][j] << ' ';
        fout << '\n';}*/

    for(i=1;i<=n;i++)
        if(!uz[i].plus && !uz[i].minus)
        {
            parcurgplus(i);
            //for(j=1;j<=n;j++)
                //fout << uz[j].plus << ' ' << uz[j].minus << '\n';
            parcurgminus(i);
            //fout << '\n';
            //for(j=1;j<=n;j++)
                //fout << uz[j].plus << ' ' << uz[j].minus << '\n';
            componenta(i);

            //fout << '\n';
        }

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

void parcurgplus(int k)
{int i;

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

}

void parcurgminus(int k)
{int i;

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

}

void componenta(int k)
{int i;

    c++;
    for(i=k;i<=n;i++)
    {
        if(uz[i].plus && uz[i].minus)
        {
            ctc[c][0]++;
            ctc[c][ctc[c][0]] = i;
        }
        else
        {
            uz[i].plus = false;
            uz[i].minus = false;
        }
    }
}