Cod sursa(job #1335301)

Utilizator bogdanmarin69Bogdan Marin bogdanmarin69 Data 5 februarie 2015 13:03:27
Problema Componente tare conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <fstream>
#include <bitset>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
#define MAX 100003
vector <int> gr[MAX], comp[MAX];
stack <int> s, afis;
bitset <MAX> bs;
int n, m, id[MAX], low[MAX], nc, urm;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
void tarjan(int nod){
    id[nod] = low[nod] = ++urm;
    s.push(nod);
    bs[nod] = 1;
    for(unsigned i=0; i<gr[nod].size(); i++)
        if(id[gr[nod][i]]==0){
            tarjan(gr[nod][i]);
            low[nod] = min(low[nod], low[gr[nod][i]]);
        }
        else
            if(bs[nod]==1)
                low[nod] = min(low[nod], low[gr[nod][i]]);
    if(id[nod] == low[nod]){
        nc++;
        int v;
        do{
            v = s.top();
            s.pop(); bs[v] = 0;
            afis.push(v);
        }while(v!=nod);
    }

}
int main()
{
    int i, u, v;
    fin>>n>>m;
    for(i=1; i<=m; i++){
        fin>>u>>v;
        gr[u].push_back(v);
    }
    for(i=1; i<=n; i++)
        if(id[i]==0)
            tarjan(i);
    fout<<nc;
    while(!afis.empty()){
        int v = afis.top();
        afis.pop();
        if(id[v] == low[v]) fout<<'\n';
        fout<<v<<' ';
    }
    return 0;
}