Cod sursa(job #2195412)

Utilizator dobrandreiAndrei Dobra dobrandrei Data 16 aprilie 2018 12:38:24
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <stdio.h>
#include <cstring>
#include <vector>
using namespace std;
FILE *f,*g;

int n,m,sol;
int start[100002],startGT[100002],t[2][400002],tGT[2][400002],been[100002],st[100002];
vector <int> solution[100002];
void read()
{
  fscanf(f,"%d %d",&n,&m);
  int k=0,kk=0,x,y;
  for(int i=1;i<=m;i++)
  {
    fscanf(f,"%d %d",&x,&y);
    k++;
    t[0][k]=y;
    t[1][k]=start[x];
    start[x]=k;

    kk++;
    tGT[0][kk]=x;
    tGT[1][kk]=startGT[y];
    startGT[y]=kk;
  }
}

void dfs(int node)
{
  been[node]=1;
  int poz=start[node];
  while(poz)
  {
    if(!been[t[0][poz]])
      dfs(t[0][poz]);
    poz=t[1][poz];
  }
  st[++st[0]]=node;
}

void dfst(int node)
{
  been[node]=1;
  int poz=startGT[node];
  while(poz)
  {
    if(!been[tGT[0][poz]])
      dfst(tGT[0][poz]);
    poz=tGT[1][poz];
  }
  solution[sol].push_back(node);
}

int main()
{
    f=fopen("ctc.in","r");
    g=fopen("ctc.out","w");
    read();
    for(int i=1;i<=n;i++)
      if(!been[i])
        dfs(i);
    for(int i=1;i<=n;i++)
      been[i]=0;
    for(int i=n;i>=1;i--)
      if(!been[st[i]])
      {
        sol++;
        dfst(st[i]);
      }
    fprintf(g,"%d\n",sol);
    for(int i=1;i<=sol;i++,fprintf(g,"\n"))
    {
      for(int j=0;j<solution[i].size();j++)
        fprintf(g,"%d ",solution[i][j]);
    }
    return 0;
}