Cod sursa(job #1415634)

Utilizator alex1096Postolache Alex alex1096 Data 5 aprilie 2015 16:35:04
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 2.45 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;             // stare imi arata daca acel nod face parte dintr-o compnenta conexa(plux minus), daca a facut parte(3)...
vector<int> nod_plus[nmax];    //graful normal
vector<int> nod_minus[nmax];    // graful transpus
vector<int> conexe[nmax];       // vectorul de compnente conexe
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);            // cautare pe graf normal
    negativ_DFS(sursa);             // cautare pe graf transpus
    int ok=1;
    for(int i=1;i<=N;++i)
    {
        if(stare[i]==plusminus && ok==1)  //daca este primul termen din elementele componentei conexe maresc si numarul de componente conexe(cred ca mergea si fara if, iar k maresc inainte de for)
        {
            conexe[++k].push_back(i);
            ok=0;
        }
        else if(stare[i]==plusminus)
            conexe[k].push_back(i);
        if(stare[i]!=plusminus && stare[i]!=3) // daca e doar plus sau minus atunci setez la 0
            stare[i]=0;
        else stare[i]=3;            // daca nodul nu face parte din din ala compnenta conexa sau actuala il setez ca fiind din alta compnenta conexa
    }
}
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);    //crearea graf normal
        nod_minus[vecin].push_back(sursa);  //creare graf transpus
    }
    for(int i=1;i<=N;++i)
        if(stare[i]!=3)             //daca nodul nu face parte din alta compnenta conexa incep cautarea din acel punct
            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;
}