Cod sursa(job #853869)

Utilizator chimistuFMI Stirb Andrei chimistu Data 12 ianuarie 2013 14:02:05
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.74 kb
#include <cstdio>
#include <cstdlib>
#include <vector>
#define maxn 100001

using namespace std;

FILE*f=fopen("ctc.in","r");
FILE*g=fopen("ctc.out","w");

vector<int>G[maxn];
vector<int>Gt[maxn],sol[maxn];
int stiva[maxn],jos,sus,viz[maxn],nrcomp=0,comp[maxn],q,n,m;

void parcurgere(int nod)
{
     vector<int>::iterator it;
     if (viz[nod]==1)
        return;
     viz[nod]=1;
     for(it=G[nod].begin();it!=G[nod].end();++it)
         if (viz[*it]==0)
            parcurgere(*it);
     stiva[sus++]=nod;
}

void parcurgere2(int nod)
{
     vector<int>::iterator it;
     if (viz[nod]==-1)
        return;
     viz[nod]=-1;
     q++;
     comp[q]=nod;
     for (it=Gt[nod].begin();it!=Gt[nod].end();++it)
         if (viz[*it]!=-1)
            parcurgere2(*it);
}
void adauga()
{
       int i;
       nrcomp++;
       for (i=1;i<=q;i++)
           sol[nrcomp].push_back(comp[i]);
}

     

int main()
{
    int a,b,i;
    vector<int>::iterator it;
    fscanf(f,"%d%d",&n,&m);
    for (i=1;i<=m;i++)
    {
        fscanf(f,"%d%d",&a,&b);
        G[a].push_back(b);
        Gt[b].push_back(a);
        }
    jos=0;sus=0;
    for (i=1;i<=n;i++)
        viz[i]=0;
    for (i=1;i<=n;i++)
        if (viz[i]==0)
           parcurgere(i);
    sus--;
    while (sus>jos)
    {     
          q=0;
          if (viz[stiva[sus]]!=-1)
          {
              parcurgere2(stiva[sus]);
              adauga();
              }
          sus--;
          }
    fprintf(g,"%d \n",nrcomp);
    for (i=1;i<=nrcomp;i++)
    {
        for (it=sol[i].begin();it!=sol[i].end();++it)
            fprintf(g,"%d ",*it);
        fprintf(g,"\n");
        }
    return 0;
}