Cod sursa(job #951608)

Utilizator mihai10stoicaFMI - Stoica Mihai mihai10stoica Data 21 mai 2013 00:14:40
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<stack>
#define MAXN 100001
using namespace std;

vector<int> G[MAXN],GT[MAXN];
int viz[MAXN],n,m;
stack<int> st;
vector<int> comp;
vector< vector<int> > sol;

void dfplus(int x)
{
    viz[x]=1;
    vector<int>::iterator it;
    for(it=G[x].begin();it!=G[x].end();it++)
        if(viz[*it] == 0)
            dfplus(*it);
    st.push(x);
}
void dfminus(int x)
{
    viz[x]=-1;
    vector<int>::iterator it;
    for(it=GT[x].begin();it!=GT[x].end();it++)
        if(viz[*it]!=-1)
            dfminus(*it);
    comp.push_back(x);
}
int main()
{
    ifstream in ("ctc.in");
    in>>n>>m;
    int x,y,i;
    while(m--)
    {
        in>>x>>y;
        G[x].push_back(y);
        GT[y].push_back(x);
    }
    in.close();

    for(i=1;i<=n;i++)
        if(viz[i]==0)
            dfplus(i);
    while(!st.empty())
    {
        x=st.top();st.pop();
        if(viz[x]!=-1)
        {
            dfminus(x);
            sol.push_back(comp);
            comp.clear();
        }
    }
    ofstream out ("ctc.out");
    vector<int>::iterator it;
    out<<sol.size()<<"\n";
    for(i=0;i<sol.size();i++)
    {
        for(it=sol[i].begin();it!=sol[i].end();it++)
            out<<*it<<" ";
        out<<"\n";
    }
    out.close();
    return 0;
}