Cod sursa(job #2346705)

Utilizator corina_dimitriuDimitriu Corina corina_dimitriu Data 17 februarie 2019 23:18:55
Problema Componente tare conexe Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.85 kb
#include <fstream>
#include <vector>
#include <queue>
#define NMAX 100005

using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
void citire();
void afisare();
void BFSp(int nod);
void BFSm(int nod);
int N,M,cnt;
int viz[NMAX];
vector <int> g[NMAX],gt[NMAX],rez[NMAX];
queue <int> q;
int main()
{int i,j;
    citire();
    for(i=1;i<=N;i++)
        if(viz[i]!=-1)
           {cnt++;
            viz[i]=1;BFSp(i);
            viz[i]=-1;
            rez[cnt].push_back(i);
            BFSm(i);
           }
    afisare();
    return 0;
}
void citire()
{int i,ei,ef;
   fin>>N>>M;
   for(i=1;i<=M;i++)
       {
            fin>>ei>>ef;
            g[ei].push_back(ef);
            gt[ef].push_back(ei);
       }
}
void BFSp(int nod)
{
 int x;
 vector <int>::iterator it;
 while(q.size())
       q.pop();
 q.push(nod);
 while(q.size())
    {
         x=q.front();
         q.pop();
         for(it=g[x].begin();it!=g[x].end();it++)
             if(!viz[*it])
               {
                 viz[*it]=1;
                 q.push(*it);
               }
    }

}
void BFSm(int nod)
{
 int x;
 vector <int>::iterator it;
 while(q.size())
       q.pop();
 q.push(nod);
 while(q.size())
    {
         x=q.front();
         q.pop();
         for(it=gt[x].begin();it!=gt[x].end();it++)
             if(viz[*it]==1)
               {
                 viz[*it]=-1;
                 q.push(*it);
                 rez[cnt].push_back(*it);
               }
               else
               if(viz[*it]==0)
               {
                 q.push(*it);
               }
    }
}
void afisare()
{int i;
    fout<<cnt<<'\n';
    vector <int>::iterator it;
    for(i=1;i<=cnt;i++)
        {for(it=rez[i].begin();it!=rez[i].end();it++)
             fout<<*it<<' ';
         fout<<'\n';
        }
}