Cod sursa(job #2157097)

Utilizator Horia14Horia Banciu Horia14 Data 9 martie 2018 11:17:40
Problema Componente biconexe Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 2.18 kb
#include<cstdio>
#include<vector>
#include<stack>
#define MAX_N 100000
using namespace std;

vector<int>g[MAX_N + 1], comp[MAX_N + 1];
stack<pair<int, int> >st;
int visitedTime[MAX_N + 1], lowTime[MAX_N + 1], p[MAX_N + 1], n, m, time, nr;
bool visited[MAX_N + 1];

void readGraph() {
    int x, y;
    FILE *fin = fopen("biconex.in","r");
    fscanf(fin,"%d%d",&n,&m);
    for(int i = 0; i < m; i++) {
        fscanf(fin,"%d%d",&x,&y);
        g[x].push_back(y);
        g[y].push_back(x);
    }
    fclose(fin);
}

void popStack(int x, int y) {
    bool ok;
    vector<int>sol;
    vector<int>::iterator it;
    vector<int>::iterator it2;
    int i, j;
    do {
        i = st.top().first;
        j = st.top().second;
        st.pop();
        sol.push_back(i), sol.push_back(j);
    }while(x != i || y != j);
    for(it = sol.begin(); it != sol.end(); it++) {
        ok = false;
        for(it2 = comp[nr].begin(); it2 != comp[nr].end() && !ok; it2++)
            if(*it2 == *it)
                ok = true;
        if(!ok)
            comp[nr].push_back(*it);
    }
    nr++;
}

void DFS(int node) {
    vector<int>::iterator it;
    visited[node] = true;
    visitedTime[node] = lowTime[node] = time++;
    for(it = g[node].begin(); it != g[node].end(); it++) {
        if(p[node] == *it)
            continue;
        if(!visited[*it]) {
            p[*it] = node;
            st.push(make_pair(node,*it));
            DFS(*it);
            if(visitedTime[node] <= lowTime[*it])
                popStack(node,*it); // node este punct de articulatie
                                    // eliminam muchiile din stiva pana la intalnirea muchiei (node, *it)
            else lowTime[node] = min(lowTime[node],lowTime[*it]);
        } else lowTime[node] = min(lowTime[node],visitedTime[*it]);
    }
}

void printComp() {
    FILE *fout = fopen("biconex.out","w");
    fprintf(fout,"%d\n",nr);
    for(int i = 0; i < nr; i++) {
        for(int j = 0; j < comp[i].size(); j++)
            fprintf(fout,"%d ",comp[i][j]);
        fprintf(fout,"\n");
    }
    fclose(fout);
}

int main() {
    readGraph();
    DFS(1);
    printComp();
    return 0;
}