Cod sursa(job #2083763)

Utilizator flaviu_2001Craciun Ioan-Flaviu flaviu_2001 Data 8 decembrie 2017 09:01:10
Problema Componente biconexe Scor 12
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <bits/stdc++.h>

using namespace std;

int n, m, dfn[100005], low[100005], p, sol = 1;
vector<int> v[100005];
bool ok[100005];

void df(int x, int tata)
{
    ok[x] = 1;
    low[x] = dfn[x] = ++p;
    int mx = -1;
    for (vector<int>::iterator it = v[x].begin(); it != v[x].end(); ++it)
        if(!ok[*it]){
            df(*it, x);
            low[x] = min(low[x], low[*it]);
            mx = max(mx, low[*it]);
        }else if(*it != tata){
            low[x] = min(low[x], dfn[*it]);
        }
    if(mx >= dfn[x]){
        //cout << x << "\n";
        ++sol;
    }
}

int main()
{
    ifstream fin ("biconex.in");
    ofstream fout ("biconex.out");
    fin >> n >> m;
    while(m--){
        int x, y;
        fin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for (int i = 1; i <= n; ++i)
        if(!ok[i]){
            int nrfii = 0;
            dfn[i] = low[i] = ++p;
            ok[i] = 1;
            for (vector<int>::iterator it = v[i].begin(); it != v[i].end(); ++it)
                if(!ok[*it]){
                    ++nrfii;
                    df(*it, i);
                }
            if(nrfii > 1){
                //cout << i << "\n";
                ++sol;
            }
        }
    fout << sol << "\n";
    fin.close();
    fout.close();
    return 0;
}