Cod sursa(job #1496212)

Utilizator BogdanisarBurcea Bogdan Madalin Bogdanisar Data 4 octombrie 2015 16:33:21
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.67 kb
#include<iostream>
#include<fstream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<bitset>
#include<cstring>
#include<queue>
#include<stack>

#define ull unsigned long long
#define ll long long
#define pb push_back
#define FOR(a,b,c) for (int a=b;a<=c; ++a)
#define ROF(a,b,c) for (int a=b;a>=c; --a)
#define Nmax 100010

// algoritmul tarjan

using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int N,M,nrcomp,nr;
int index[Nmax],lowest[Nmax];

vector<int> v[Nmax];
vector<int> componente[Nmax];
vector<int> st;
bitset<Nmax> instack;

void dfs(int);

int main()
{
    f>>N>>M;
    FOR (i,1,M) {
        int x,y;
        f>>x>>y;
        v[x].pb(y);
    }
    FOR (i,1,N) {
        if (!index[i]) {
            dfs(i);
        }
    }
    g<<nrcomp<<'\n';
    FOR (i,1,nrcomp) {
        for (unsigned int k=0;k<componente[i].size();++k) {
            g<<componente[i][k]<<' ';
        }
        g<<'\n';
    }
    f.close();g.close();
    return 0;
}

void dfs(int nod) {
    index[nod]=lowest[nod]=++nr;
    st.pb(nod);
    instack.set(nod,1);
    for (unsigned int k=0;k<v[nod].size();++k) {
        if (!index[v[nod][k]]) {
            dfs(v[nod][k]);
            lowest[nod]=min(lowest[nod],lowest[v[nod][k]]);
        }
        else if (instack.test(v[nod][k])) {
            lowest[nod]=min(lowest[nod],lowest[v[nod][k]]);
        }
    }
    if (index[nod]==lowest[nod]) {
        ++nrcomp;
        int top;
        do {
            top=st.back();
            st.pop_back();
            instack.set(top,0);
            componente[nrcomp].pb(top);
        }
        while (top!=nod);
    }
}