Cod sursa(job #1441044)

Utilizator petremariaPetre Maria petremaria Data 23 mai 2015 15:14:32
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>
#define MAXIM 100005
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector<int> gg[MAXIM], gt[MAXIM], ctc[MAXIM/2];
int stack[MAXIM], varf, nrc;
bitset <MAXIM> vizitat;
void dfs(int nod)
{
    vizitat[nod]=1;
    for( int i=0; i<gg[MAXIM].size();i++)
        if(vizitat[gg[nod][i]]==0)
            dfs(gg[nod][i]);
    stack[++varf]=nod;

}
void dfss(int nod)
{
    vizitat[nod]=0;
    ctc[nrc].push_back(nod);
    for(int i=0; i<gt[nod].size();i++)
    if(vizitat[gt[nod][i]]==1)
        dfs(gt[nod][i]);
}
int main()
{
    int n,m, i,x,y;
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y;
        gg[x].push_back(y);
        gt[y].push_back(x);
    }
    for(i=1;i<=n;i++)
        if(vizitat[i]==0)
            dfs(i);
    for(i=n; i>=1;i--)
        if(vizitat[stack[i]]==1)
    {
        nrc++;
        dfss(stack[i]);
    }
        g<<nrc;
        for(i=1;i<=nrc;i++)
        {
            for(int j=0;j<ctc[i].size();j++)
                g<<ctc[i][j];
            g<<"\n";
        }

    return 0;
}