Cod sursa(job #1376625)

Utilizator witselWitsel Andrei witsel Data 5 martie 2015 18:06:45
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.72 kb
#include <iostream>
#include <fstream>
#include <vector>
#define plus 1
#define minus -1
#define plusminus 2
using namespace std;
const int nmax=100001;
int N,M,stare[nmax],k;
vector<int> nod_plus[nmax];
vector<int> nod_minus[nmax];
vector<int> conexe[nmax];
void pozitiv_DFS(int sursa)
{
    stare[sursa]=plus;
    for(int i=0;i<nod_plus[sursa].size();++i)
        {
            if(stare[nod_plus[sursa][i]]!=plus && stare[nod_plus[sursa][i]]!=3)
                pozitiv_DFS(nod_plus[sursa][i]);
        }
}
void negativ_DFS(int sursa)
{
    if(stare[sursa]==plus)
        stare[sursa]=plusminus;
    else
        stare[sursa]=minus;
    for(int i=0;i<nod_minus[sursa].size();++i)
        if(stare[nod_minus[sursa][i]]==plus)
            negativ_DFS(nod_minus[sursa][i]);
}
void search(int sursa)
{
    pozitiv_DFS(sursa);
    negativ_DFS(sursa);
    int ok=1;
    for(int i=1;i<=N;++i)
    {
        if(stare[i]==plusminus && ok==1)
        {
            conexe[++k].push_back(i);
            ok=0;
        }
        else if(stare[i]==plusminus)
            conexe[k].push_back(i);
        if(stare[i]!=plusminus && stare[i]!=3)
            stare[i]=0;
        else stare[i]=3;
    }
}
int main()
{
    ifstream fin("ctc.in");
    ofstream fout("ctc.out");
    fin>>N>>M;
    int sursa,vecin;
    for(int i=1;i<=M;++i)
    {
        fin>>sursa>>vecin;
        nod_plus[sursa].push_back(vecin);
        nod_minus[vecin].push_back(sursa);
    }
    for(int i=1;i<=N;++i)
        if(stare[i]!=3)
            search(i);
    fout<<k<<"\n";
    for(int i=1;i<=k;++i)
    {
        for(int j=0;j<conexe[i].size();++j)
            fout<<conexe[i][j]<<" ";
        fout<<"\n";
    }
    return 0;
}