Cod sursa(job #806105)

Utilizator Theorytheo .c Theory Data 1 noiembrie 2012 20:28:10
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.85 kb
#include<fstream>
#include<vector>
#define plus plus1
#define minus minus1
#define nmax 100007
using namespace std;

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

vector <int> G[nmax];
vector <int> Gt[nmax];
int N, M, nr;
bool o[nmax];
bool plus[nmax];
bool minus[nmax];
vector <int> CTC[nmax];
void read()
{

    fin >>N >>M;
    for(int i = 1; i <= M; i++)
    {
        int x, y;
        fin >>x>>y;
        G[x].push_back(y);
        Gt[y].push_back(x);
    }

}
void marcheaza_plus(int x)
{
    plus[x] = true;
    for(int i = 0 ;i < G[x].size(); i++)
    {
        if(plus[G[x][i]] == false && o[G[x][i]] == false)
            marcheaza_plus(G[x][i]);
    }
}

void sterge(int x)
{
    plus[x] = false;
    for(int i = 0 ;i < G[x].size(); i++)
    {
        if(plus[G[x][i]] == true  )
        sterge(G[x][i]);
    }
}

void sterge2(int x)
{

    minus[x] = false;
    for(int i = 0 ;i < Gt[x].size(); i++)
    {
        if(minus[Gt[x][i]] == false)
        {
            sterge2(Gt[x][i]);
        }
    }
}
void marcheaza_minus(int x)
{
    minus[x] = true;
    if(plus[x] == true)
    {
        CTC[nr].push_back(x);
        o[x] = true;
    }

    for(int i = 0; i < Gt[x].size(); i++)
    {
        if(minus[Gt[x][i]] == false && o[Gt[x][i]] == false)

            marcheaza_minus(Gt[x][i]);

    }
}
int main()
{
    read();
    for(int i = 1; i <= N ; i++)
    {
        if(o[i] == false)
        {
            nr++;
            marcheaza_plus(i);
            marcheaza_minus(i);
            sterge(i);
            sterge2(i);
        }

    }
    fout << nr <<'\n';
    for(int i = 1; i <= nr; i++)
    {
        for(int j = 0 ; j < CTC[i].size(); j++)
        {
            fout << CTC[i][j]<<" ";
        }
        fout << '\n';

    }
    fin.close();
    return 0;
}