Cod sursa(job #2012217)

Utilizator rangal3Tudor Anastasiei rangal3 Data 18 august 2017 12:31:00
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include <fstream>
#include <vector>
#include <queue>
#define in "ctc.in"
#define out "ctc.out"
#define N 100003

using namespace std;

ifstream fin(in);
ofstream fout(out);

vector<int> g[N],gt[N];  // gt - graf transpus

queue<int> coada[N];

bool f[N],ft[N],fa[N];
int n,m,x,y;
int nctc;

inline void DFS(int nod)
{
    vector<int>::iterator it;
    f[nod] = 1;
    for(it = g[nod].begin(); it != g[nod].end(); ++it)
        if(!f[*it])
            DFS(*it);
}

inline void DFSt(int nod)
{
    vector<int>::iterator it;
    ft[nod] = 1;
    for(it = gt[nod].begin(); it != gt[nod].end(); ++it)
        if(!ft[*it])
            DFSt(*it);
}

int main()
{
    fin>>n>>m;
    while(m--)
    {
        fin>>x>>y;
        g[x].push_back(y);
        gt[y].push_back(x);
    }

    for(int i=1; i<=n; ++i)
        if(!fa[i])
        {
            DFS(i);
            DFSt(i);

            ++nctc;
            for(int i=1; i<=n; ++i)
                if(f[i] == ft[i] && f[i] == 1)
                {
                    coada[nctc].push(i);
                    fa[i] = 1;
                }
            for(int i=1; i<=n; ++i)
                f[i] = ft[i] = 0;
        }

    fout<<nctc<<"\n";
    for(int i=1; i<=nctc; ++i)
    {
        while(coada[i].empty() == 0)
        {
            fout<<coada[i].front()<<" ";
            coada[i].pop();
        }
        fout<<"\n";
    }

    fin.close(); fout.close();
    return 0;
}