Cod sursa(job #1669195)

Utilizator alex.vasiuVasiu Alexandru alex.vasiu Data 30 martie 2016 15:00:00
Problema Componente tare conexe Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.99 kb
#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int n,m;
vector <int> G[100005],/*G1[100005],v,*/rez[100005];
int S[100005],nr;
struct vertex{
    int l, id;
    bool stack;
}ex{0,0,0};
vector <vertex> marcat;
int k;
stack <int> s;
int index;
/*void dfs1(int nod)
{
    marcat[nod]=1;
    for(auto p : G1[nod])
        if(!marcat[p])
            dfs1(p);
    v.push_back(nod);
}
void dfs2(int nod,int comp)
{
    marcat[nod]=comp;
    rez[comp-1].push_back(nod);
    for(auto p : G[nod])
        if(!marcat[p])
            dfs2(p,comp);
}*/

void tarjan(int nod)
{
    marcat[nod].id=index;
    marcat[nod].l=index;
    index++;
    //S[++nr]=nod;
    s.push(nod);
    marcat[nod].stack=true;
    for(auto w : G[nod])
        if(!marcat[w].id)
            tarjan(w), marcat[nod].l=min(marcat[nod].l, marcat[w].l);
        else
        if(marcat[w].stack)
            marcat[nod].l=min(marcat[nod].l, marcat[w].l);

    if(marcat[nod].id == marcat[nod].l)
     {
        int x;
         k++;
        do{
            x=s.top();
            s.pop();
            marcat[x].stack=0;
            rez[k-1].push_back(x);

        }while(x!=nod);

    }
}
int main()
{
    f>>n>>m;
    marcat.resize(n+1);
    fill(marcat.begin(),marcat.end(),ex);
    for(int i=0; i<m; i++)
    {
        int a,b;
        f>>a>>b;
        G[a].push_back(b);
        //G1[b].push_back(a);
    }
    for(int i=1;i<=n;i++)
        if(!marcat[i].id)
              tarjan(i);


    /*for(int i=1; i<=n; i++)
        if(!marcat[i])
            dfs1(i);
    fill(begin(marcat),end(marcat),0);
    int nr=v.size()-1;
    for(; nr>=0; nr--)
        if(!marcat[v[nr]])
        {
            dfs2(v[nr],k+1);
            k++;
        }*/
    g<<k<<"\n";
    for(int i=0; i<k; i++)
    {
        for(auto x:rez[i])
            g<<x<<" ";
        g<<"\n";
    }
}