Cod sursa(job #1875814)

Utilizator ifrimencoAlexandru Ifrimenco ifrimenco Data 11 februarie 2017 16:46:14
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <bits/stdc++.h>

using namespace std;
vector <set  <int> >gr;
vector <set  <int> > gr2;
vector <set <int> >gr3;
int viz[100];
vector <int> postordine;
ofstream g("ctc.out");
void DFS (int x)
{
    viz[x]=1;
    set <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);
   set<int>::iterator it;
   for (it=gr2[x-1].begin();it!=gr2[x-1].end();++it)
    if (viz[*it])
    DFST(*it,y);
}
int main()
{
    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].insert(b);
        gr2[b-1].insert(a);
   }
set<int> q;

for (i=1;i<=n;++i)
    if (!viz[i]) DFS(i);
    for (i=0;i<n;++i)
        if (viz[postordine[i]+1]) {gr3.push_back(q);DFST(postordine[i]+1,nr);nr++;}
        g << nr << "\n";
        for (i=0;i<nr;++i)
        {
            set <int>::iterator it;
            for (it=gr3[i].begin();it!=gr3[i].end();++it)
                g << *it << " ";
            g << "\n";
        }

    return 0;
}