Cod sursa(job #652125)

Utilizator mihai995mihai995 mihai995 Data 23 decembrie 2011 00:36:28
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <fstream>
#include <vector>
using namespace std;

const int N=100005;
int v[N],n;
bool use[N];
vector<int> a[N],b[N],rez[N];

ifstream in("ctc.in");
ofstream out("ctc.out");

void dfs(int x,int val)
{
    v[x]=val;
    for (vector<int>::iterator i=a[x].begin();i!=a[x].end();i++)
        if (!v[*i])
            dfs(*i,val);
}

void dfs(vector<int> &rez,int x)
{
    rez.push_back(x);
    use[x]=true;
    for (vector<int>::iterator i=b[x].begin();i!=b[x].end();i++)
        if (!use[*i] && v[x]==v[*i])
            dfs(rez,*i);
}

int main()
{
    int nr=0,x,y,val=0,m;
    in>>n>>m;
    while (m--)
    {
        in>>x>>y;
        a[x].push_back(y);
        b[y].push_back(x);
    }
    for (int i=1;i<=n;i++)
    {
        if (!v[i])
            dfs(i,++val);
        if (!use[i])
            dfs(rez[++nr],i);
    }
    out<<nr<<"\n";
    for (int i=1;i<=nr;i++)
    {
        for (vector<int>::iterator j=rez[i].begin();j!=rez[i].end();j++)
            out<<(*j)<<" ";
        out<<"\n";
    }
    return 0;
}