Cod sursa(job #527559)

Utilizator APOCALYPTODragos APOCALYPTO Data 31 ianuarie 2011 21:17:47
Problema Flux maxim Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.34 kb
using namespace std;
#include<iostream>
#include<fstream>
#include<vector>
#define pb push_back
#define nmax 100005

/*
In acesta sursa se vede clar de ce trebuie facute anumite lucruri in algoritmul Kosaraju
Exista 3 situatii posibile
  -ajungem intr-un nod=> poate fi din aceiasi componenta tare conexa cu nodu lde start
  -nu ajungem intr-un nod => nu puteam ajunge la el in graful G
  => nodul nu poate face parte din aceiasi componenta conexa
  Dar daca avem o muchie inversa intre u(din componeta conexa Y ) si v?
  Este clar ca ne afla in situatia 2 pentru graful G dar in graful muchia va fi de la u la v
  si daca pormin din componenta lui u(Y) atunci il vom include si pe v care nu face parte din Y.
  Din acest motiv componetele conexe trebuie puse in ordinea inversa in care au fost gasite
  ca sa nu ajungem din v la u

  Nodurile aceiasi componeta pot fi lasate in ordinea in care sunt gasite.


*/


struct nod{
int lg;};
vector<nod> G[nmax];
vector<nod> TG[nmax];
vector<int> ans[nmax];
vector<int> q[nmax];
ofstream fout("ctc.out");
int N,M,viz[nmax],nr,postord[nmax],E;
void  DFS(int u)
{
    if(viz[u]) return;
    viz[u]=1;
    //postord[++nr]=u;
    q[E].push_back(u);
    vector<nod>::iterator it;
    for(it=G[u].begin();it<G[u].end();it++)
    {
        DFS(it->lg);
    }

}
void DFS2(int u)
{
    if(!viz[u]) return;
    viz[u]=0;
    vector<nod>::iterator it;
    for(it=TG[u].begin();it<TG[u].end();it++)
    {
        DFS2(it->lg);

    }
    ans[nr].pb(u);
}
void solve()
{
    int i,j;
    for(i=1;i<=N;i++)
     if(!viz[i])
      {   E++;
          DFS(i);

      }
      nr=0;

    /*for(i=1;i<=N;i++)
    {
        cout<<postord[i]<<" ";
    }*/


    for(i=E;i>=1;i--)
    {
    for(j=0;j<q[i].size();j++)
     {
        // cout<<q[i][j]<<" ";
    if(viz[q[i][j]])
      {nr++;
      DFS2(q[i][j]);
      }
    }
    //cout<<"\n";
    }
    fout<<nr<<"\n";
    for(i=1;i<=nr;i++)
    {
     for(j=0;j<ans[i].size();j++)
       fout<<ans[i][j]<<" ";
     fout<<"\n";
    }
}

void cit()
{
    ifstream fin("ctc.in");
    int i,x,y;
    fin>>N>>M;
    for(i=1;i<=M;i++)
    {
        fin>>x>>y;
        G[x].pb((nod){y});
        TG[y].pb((nod){x});
    }

    fin.close();

}

int main()
{
    cit();
    solve();
    fout.close();
    return 0;
}