Cod sursa(job #2427542)

Utilizator PrekzursilAndrei Visalon Prekzursil Data 31 mai 2019 23:20:12
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.55 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
using namespace std;
vector<vector<int> > Graph(100001), Sol(100001);
stack<int> S;
pair<int, int> P[100001];
int N, M, i, j, V, VP;
bool Check[100001];
void DFS(int i);
int main()
{
    freopen("biconex.in", "r", stdin);
    freopen("biconex.out", "w", stdout);
    scanf("%d%d", &N, &M);
    for(i=1; i<=N; ++i) Graph[i].push_back(0);
    for(i=1; i<=M; ++i){
        int x, y;
        scanf("%d%d", &x, &y);
        Graph[x].push_back(y);
        Graph[y].push_back(x);
        ++Graph[x][0];
        ++Graph[y][0];
    }
    for(i=1; i<=N; ++i) if(Check[i]==false) DFS(i);
    printf("%d\n", V);
    for(i=1; i<=V; ++i){
        for(j=0; j<Sol[i].size(); ++j) printf("%d ", Sol[i][j]);
        printf("\n");
    }
    return 0;
}
void DFS(int i){
    int j;
    P[i].first=P[i].second=++VP;
    Check[i]=true;
    S.push(i);
    for(j=1; j<=Graph[i][0]; ++j){
        if(Check[Graph[i][j]]==false){
            DFS(Graph[i][j]);
            P[i].second=min(P[i].second, P[Graph[i][j]].second);
            if(P[i].first<=P[Graph[i][j]].first && P[i].first<=P[Graph[i][j]].second){
                ++V;
                while(S.top()!=Graph[i][j]){
                    Sol[V].push_back(S.top());
                    S.pop();
                }
                Sol[V].push_back(S.top());
                S.pop();
                Sol[V].push_back(i);
            }
        }
        else P[i].second=min(P[i].second, P[Graph[i][j]].first);
    }
    return;
}