Cod sursa(job #2576110)

Utilizator ShouldTryAdam Robert Mihai ShouldTry Data 6 martie 2020 17:20:26
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
using namespace std;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
vector <int > v[100005], vt[100005], ctc[100005];
stack <int > s;
int n, m, beenthere[100005], c;
void citire()
{fin >> n >> m;
 int a, b;
 for (int i=1;i<=m;i++)
     {fin >> a >> b;
      v[a].push_back(b);
      vt[b].push_back(a);
     }
}
void dfs (int k)
{beenthere[k]=1;
 for (int i=0;i<v[k].size();i++)
      if(beenthere[v[k][i]]==0)
          dfs(v[k][i]);
s.push(k);
}
void dfst (int k)
{beenthere[k]=2;
 ctc[c].push_back(k);
 for (int i=0;i<vt[k].size();i++)
      if(beenthere[vt[k][i]]==1)
           dfst(vt[k][i]);
}
int main()
{citire ();
 for (int i=1;i<=n;i++)
      if(beenthere[i]==0)
         dfs(i);
 while (!s.empty())
       {int nod=s.top();
        s.pop();
        if(beenthere[nod]==1)
          {c++;
           dfst(nod);
          }
       }
 fout << c << endl;
 for (int i=1;i<=c;i++)
     {sort(ctc[i].begin(),ctc[i].end());
      for (int j=0;j<ctc[i].size();j++)
           fout << ctc[i][j] << " ";
      fout << endl;
     }
    return 0;
}