Cod sursa(job #2140219)

Utilizator AndreidgDragomir Andrei Valentin Andreidg Data 23 februarie 2018 08:16:18
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.64 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
const int N = 100005;
ifstream f("ctc.in");
ofstream g("ctc.out");

vector <int> V[N];
vector <int> TR[N];
vector <int> adj;
vector <int> sol[N];
int  n,m,nr;
bool pluss[N];
bool minuss[N];

void dfs(int poz){

    int sz     = V[poz].size();
    pluss[poz] = 1;
    for(int i =0; i< sz; i++){

        int nx = V[poz][i];
        if(pluss[nx] == 0&&minuss[nx]==0)
            dfs(nx);
    }
    adj.push_back(poz);
}

void dfm(int poz){

    int sz     = TR[poz].size();
    minuss[poz] = 1;
    for(int i =0; i< sz; i++){

        int nx = TR[poz][i];
        if(pluss[nx] == 1&&minuss[nx]==0)
            dfm(nx);
    }
    sol[nr].push_back(poz);
}

void afisare(int x){

    for(int i =0 ; i< sol[x].size(); i++){
        g<<sol[x][i]<<" ";
    }
    g<<"\n";
    /*for(int i =1; i<= n; i++){
        g<<i<<" "<<pluss[i]<<" "<<minuss[i]<<"\n";
    }
    */
}
int main()
{
    f>>n>>m;
    for(int i = 1; i<= m; i++){
        int x,y;
        f>>x>>y;
        V[x].push_back(y);
        TR[y].push_back(x);
    }

    for(int i = 1; i<= n; i++){


        if(pluss[i] == 0 &&minuss[i] == 0){

            adj.clear();
            dfs(i);
            nr++;
            dfm(i);
            //afisare();
            //g<<"\n";
            for(int j = 0; j< adj.size(); j++){

                pluss[adj[j]]  = 0;
                //minuss[adj[j]] = 0;
            }

        }
    }
    g<<nr<<"\n";
    for(int i =1; i<= nr ; i++)
    {
        afisare(i);
    }
    f.close();
    g.close();
    return 0;
}