Cod sursa(job #1876486)

Utilizator ifrimencoAlexandru Ifrimenco ifrimenco Data 12 februarie 2017 13:41:07
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <bits/stdc++.h>

using namespace std;
vector <vector <int> >gr;
vector <vector <int> >gr2;
vector <set <int> >gr3;
short int viz[50001];
int nr;
bool cmp(set <int> a, set <int> b)
{
    return (a.size()<b.size());
}
vector <int> postordine;
ofstream g("ctc.out");
void DFS (int x)
{
    viz[x]=1;
    vector <int> ::iterator it;
    for (it=gr[x-1].begin();it!=gr[x-1].end();++it)
  if (!viz[*it])
  DFS(*it);
 postordine.push_back(x);
}
void DFST(int x,int y)
{
    viz[x]=0; gr3[y].insert(x);
    vector<int>::iterator it;
    for (it=gr2[x-1].begin();it!=gr2[x-1].end();++it)
 if (viz[*it])
 DFST(*it,y);
}
int main()
{
    set<int>::iterator it;
    int i, n, a, b, m;
    ifstream f("ctc.in");
 f >> n >> m;
 int nr=0;
 gr2.resize(n);
  gr.resize(n);
 for (i=1;i<=m;++i)
    {
  f >> a >> b;
  gr[a-1].push_back(b);
  gr2[b-1].push_back(a);
  }
set<int> q;

for (i=1;i<=n;++i)
if (!viz[i]) DFS(i);
vector <int>::reverse_iterator it5;
for (it5=postordine.rbegin();it5!=postordine.rend();++it5)
{   if (viz[*it5])
{gr3.push_back(q);
    DFST(*it5,nr);
    nr++;
}
}
sort (gr3.begin(),gr3.end(),cmp);

g << nr << "\n";
for (i=0;i<nr;++i)
{
 //   g << gr3[i].size() << " ";
    for (it=gr3[i].begin();it!=gr3[i].end();++it)
        g << *it << " ";
    g << "\n";
}
 return 0;
}