Cod sursa(job #1336817)

Utilizator RathebaSerbanescu Andrei Victor Ratheba Data 8 februarie 2015 11:34:38
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include <fstream>
#include <vector>
#include <stack>
#include <bitset>
#include <algorithm>

using namespace std;
#define MAX 100005

void dfs(int nod);

vector<int> graf[MAX];
stack<int> st, afis;
bitset<MAX> bit;

int vid[MAX], vlow[MAX], nextt, nc, n, m;

int main()
{
    ifstream fin("ctc.in");
    ofstream fout("ctc.out");
    int i, a, b;
    fin>>n>>m;
    for(i=1; i<=m; i++)
    {
        fin>>a>>b;
        graf[a].push_back(b);

    }
    for(i=1; i<=n; i++)
        if(!vid[i])
            dfs(i);
    fout<<nc;
    while(!afis.empty())
    {
        if(vid[afis.top()] == vlow[afis.top()])
            fout<<'\n';
        fout<<afis.top()<<' ';
        afis.pop();
    }
    return 0;
}
void dfs(int nod)
{
    int i, fiu;
    nextt++;
    vid[nod] = vlow[nod] = nextt;
    st.push(nod);
    bit[nod] = 1;
    for(i=0; i<graf[nod].size(); i++)
    {
        fiu = graf[nod][i];
        if(!vid[fiu])
        {
            dfs(fiu);
            vlow[nod] = min(vlow[nod], vlow[fiu]);
        }
        else
            if(bit[fiu])
                vlow[nod] = min(vlow[nod], vlow[fiu]);
    }
    if(vid[nod] == vlow[nod])
    {
        nc++;
        do
        {
            afis.push(st.top());
            bit[st.top()] = 0;
            st.pop();
        }while(afis.top() != nod);
    }
}