Cod sursa(job #2438861)

Utilizator CharacterMeCharacter Me CharacterMe Data 14 iulie 2019 10:57:56
Problema Componente biconexe Scor 42
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.38 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#define f first
#define s second
using namespace std;
int n, m, i, j, val[200005], v, vf;
vector<int> graph[200005], sol[200005];
bool check[200005];
stack<int> s;
pair<int, int> p[200005];
void dfs(int node);
int main()
{
    freopen("biconex.in", "r", stdin);
    freopen("biconex.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for(i=1; i<=m; ++i) {
        int x, y;
        scanf("%d%d", &x, &y);
        graph[x].push_back(y);
        graph[y].push_back(x);
    }
    dfs(1);
    //for(i=1; i<=n; ++i) printf("%d\n", val[i]);
    printf("%d\n", vf);
    for(i=1; i<=vf; ++i){
        for(auto j:sol[i]) printf("%d ", j);
            printf("\n");
    }
    return 0;
}
void dfs(int node){
    check[node]=true; s.push(node);
    p[node]={++v, v};
    for(auto i:graph[node]){
        if(check[i]==false){
            dfs(i);
            p[node].s=min(p[node].s, p[i].s);
            if(p[node].f<=p[i].f && p[node].f<=p[i].s){
                ++vf;
                while(s.top()!=node) {
                    sol[vf].push_back(s.top());
                    ++val[s.top()];
                    s.pop();
                }
                ++val[node];
                sol[vf].push_back(node);
            }
        }
        else p[node].s=min(p[node].s, p[i].f);
    }
    return;
}