Cod sursa(job #951542)

Utilizator marialivia16Chiorean Maria Livia marialivia16 Data 20 mai 2013 21:13:20
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 2.17 kb
#include <iostream>
#include<vector>
#include<stack>
#include<string>
#include<fstream>
#include<algorithm>
#define lim 100001
using namespace std;
class tconex {
    int n,m,sel[lim];
    vector<int> graf[lim],graf_tr[lim],comp;
    vector< vector<int> > sol;
    stack<int> stiva;
    fstream in,out;
public:
    tconex(string fin, string fout)
    {
        in.open(fin.c_str(), ios::in);
        out.open(fout.c_str(), ios::out);
    }
    ~tconex()
    {
        in.close();
        out.close();
    }
    void read()
    {
        int a,b;
        in>>n>>m;
        for(int i=1;i<=m;i++)
        {
            in>>a>>b;
            graf[a].push_back(b);
            graf_tr[b].push_back(a);

        }
        for(int i=1;i<=n;i++)
        {
            sel[i]=0;
        }

    }
    void dfs1(int nod)
    {
        sel[nod]=1;
        vector<int>::iterator it;
        for(it=graf[nod].begin();it<graf[nod].end();it++)
        {
            if(sel[*it]==0)
            {
                dfs1(*it);
            }
        }
        stiva.push(nod);
    }
    void dfs2(int nod)
    {
        sel[nod]=-1;
        vector<int>::iterator it;
        for(it=graf_tr[nod].begin();it<graf_tr[nod].end();it++)
        {
            if(sel[*it]!=-1)
                dfs2(*it);
        }
        comp.push_back(nod);
    }
    void solve()
    {
        for(int i=1;i<=n;i++)
        {
            if(sel[i]==0)
            {
                dfs1(i);
            }
        }
        int aux;
        while(!stiva.empty())
        {
            aux=stiva.top();
            stiva.pop();
            if(sel[aux]!=-1)
            {
                dfs2(aux);
                sol.push_back(comp);
                comp.clear();
            }
        }
        out<<sol.size()<<endl;
        vector<int>::iterator it;
        for(int i=0;i<sol.size();i++)
        {
            for(it=sol[i].begin();it<sol[i].end();it++)
            {
                    out<<*it<<" ";
            }
            out<<endl;
        }
    }
};
int main()
{
    tconex X("ctc.in","ctc.out");
    X.read();
    X.solve();
    return 0;
}