Cod sursa(job #1905631)

Utilizator roxanastRoxana Stiuca roxanast Data 6 martie 2017 09:50:34
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 kb
#include <fstream>
#include <vector>
#define NMAX 100010
#define Min(a, b) ((a) < (b) ? (a) : (b))
using namespace std;
int disc[NMAX],low[NMAX],n,m;
bool instack[NMAX];
vector <int> st;
struct nod{
int vf;
nod* urm;
};
nod* v[NMAX];

int nrctc;
vector <int> ctc[NMAX];
ifstream f("ctc.in");
ofstream g("ctc.out");

void dfs(int u){
    static int cnt=0;
    disc[u]=low[u]=++cnt;
    st.push_back(u);
    instack[u]=true;
    nod* q;
    for(q=v[u];q;q=q->urm){
        int  w=(int)q->vf;
        if(disc[w]==-1){
            dfs(w);
            low[u]=min(low[u],low[w]);
        }else{
            if(instack[w]==true)
                low[u]=min(low[u],disc[w]);
        }
    }

    int w=0;
    if(low[u]==disc[u]){
        ++nrctc;
        while(st.back()!=u)
        {
            w=(int) st.back();
            ctc[nrctc].push_back(w);
            instack[w]=false;
            st.pop_back();
        }
        w=(int)st.back();
        ctc[nrctc].push_back(w);
        instack[w]=false;
        st.pop_back();

    }
}
int main()
{
    f>>n>>m;
    for(int i=1;i<=m;i++){
        int a,b;
        f>>a>>b;
        nod* q=new nod;
        q->vf=b;
        q->urm=v[a];
        v[a]=q;
    }
    for(int i=1;i<=n;i++){
        disc[i]=low[i]=-1;
        instack[i]=false;
    }
    for(int i=1;i<=n;i++)
        if(disc[i]==-1)
            dfs(i);


    g<<nrctc<<'\n';
    for(int i=1;i<=nrctc;++i){
        for(vector <int> ::iterator it=ctc[i].begin();it<ctc[i].end();++it)
            g<<*it<<" ";
        g<<'\n';
    }
    return 0;
}