Cod sursa(job #2343600)

Utilizator BurlacuMateiBurlacu Matei BurlacuMatei Data 14 februarie 2019 09:32:33
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.07 kb
#include <fstream>
#include <vector>
#define MAX 3001

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 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].push_back(y);
        dintors[y].push_back(x);
    }

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

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

    for(i=1;i<=n;i++)
        if(!uz[i].p)
        {
            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=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]);

}

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]);

}

void componenta(int k)
{int i;

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