Cod sursa(job #2120962)

Utilizator georgerapeanuRapeanu George georgerapeanu Data 3 februarie 2018 10:23:19
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
FILE *f = fopen("ctc.in","r");
FILE *g = fopen("ctc.out","w");
vector<int> G[100005];
vector<vector<int> > ctc;
bool inst[100005];
int st[100005];
int len;
int id[100005];
int low[100005];
int lastid;
int N,M;
void dfs(int nod){
   st[++len] = nod;
   inst[nod] = 1;
   id[nod] = low[nod] = ++lastid;
   for(auto it:G[nod]){
      if(!id[it]){
         dfs(it);
      }
      if(inst[it]){
         low[nod] = min(low[nod],low[it]);
      }
   }
   if(low[nod] == id[nod]){
      vector<int> tmp;
      while(st[len] != nod){
         tmp.push_back(st[len]);
         inst[st[len]] = 0;
         len--;
      }
      tmp.push_back(st[len]);
      inst[st[len]] = 0;
      len--;
      ctc.push_back(tmp);
   }
}
int main() {
    fscanf(f,"%d %d",&N,&M);
    for(int i = 1;i <= M;i++){
       int x,y;
       fscanf(f,"%d %d",&x,&y);   
       G[x].push_back(y);
    }
    for(int i = 1;i <= N;i++){
       if(!id[i]){
          dfs(i);
       }
    }
    fprintf(g,"%d\n",(int)ctc.size());
    for(auto it:ctc){
       for(auto it2:it){
          fprintf(g,"%d ",it2);
       }
       fprintf(g,"\n");
    }
    fclose(f);
    fclose(g);
    return 0;
}