Cod sursa(job #2343995)

Utilizator RazvanPanaiteRazvan Panaite RazvanPanaite Data 14 februarie 2019 17:25:10
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.36 kb
#include <bits/stdc++.h>
#define DMAX 100010

using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

vector <int> V[DMAX];
vector <int> sol[DMAX];
stack <int> s;

int uz[DMAX];
int lowlink[DMAX];
int n,cnt,nr;

inline int minim(int x,int y)
           {if(x<y)
               return x;
            return y;
           }

void citire();
void tarjan();
void dfs(int node);
void afisare();

int main()
{citire();
 tarjan();
 afisare();
 return 0;
}
void citire()
{int i,m,x,y;
 fin>>n>>m;
 for(i=1;i<=m;i++)
     {fin>>x>>y;
      V[x].push_back(y);
     }
}
void tarjan()
{int i;
 for(i=1;i<=n;i++)
     if(!uz[i])
        dfs(i);
}
void dfs(int node)
{int i;
 uz[node]= ++cnt;
 lowlink[node]=cnt;
 s.push(node);
 for(i=0;i<V[node].size();i++)
     {if(!uz[V[node][i]])
         dfs(V[node][i]);
      if(uz[V[node][i]]>0)
         lowlink[node]=minim(lowlink[node],lowlink[V[node][i]]);
     }
 if(uz[node]==lowlink[node])
    {nr++;
     do{
        sol[nr].push_back(s.top());
        uz[s.top()]=-1;
        if(s.top()==node)
           {s.pop();
            break;
           }
           else
           s.pop();
     }while(1);
    }
}
void afisare()
{int i,j;
 fout<<nr<<'\n';
 for(i=1;i<=nr;i++)
     {for(j=0;j<sol[i].size();j++)
          fout<<sol[i][j]<<' ';
      fout<<'\n';
     }
}