Cod sursa(job #1314723)

Utilizator Alex_dudeDudescu Alexandru Alex_dude Data 12 ianuarie 2015 10:56:17
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <cstdio>
#include <cstring>
#include <vector>
#define pb push_back
#define nmax 1000
using namespace std;
FILE *f1=fopen("ctc.in","r"),*f2=fopen("ctc.out","w");
vector <int> g[nmax],gt[nmax],sol[nmax];
bool use[nmax];
int n,m,i,j,ord[nmax],nr,nrc;

void citire()
{
  fscanf(f1,"%d%d",&n,&m);
  for(int j=1;j<=m;j++)
  {
      int x,y;
      fscanf(f1,"%d%d",&x,&y);
      g[x].pb(y);
      gt[y].pb(x);
  }
}
void dfs(int nod)
{
    use[nod]=true;
    for(int j=0;j<g[nod].size();j++)
        if(!use[g[nod][j]])
        dfs(g[nod][j]);
    ord[++nr]=nod;
}
void dfst(int nod,int k)
{
    use[nod]=false; sol[k].pb(nod);
    for(int j=0;j<gt[nod].size();j++)
        if(use[gt[nod][j]])
        dfst(gt[nod][j],k);
}
int main()
{
    citire();
    for(i=1;i<=n;i++)
        if(!use[i])dfs(i);

     for(i=n;i>=1;i--)
        if(use[ord[i]])
        {
            nrc++;
            dfst(ord[i],nrc);
        }
        fprintf(f2,"%d\n",nrc);
        for(int i=1;i<=nrc;i++)
        {
            for(int j=0;j<sol[i].size();j++)
            fprintf(f2,"%d ",sol[i][j]);
            fprintf(f2,"\n");
        }
    fclose(f1);
    fclose(f2);
    return 0;
}

//Our greatest weakness lies in giving up. The most certain way to succeed is always to try just one more time.