Cod sursa(job #1370745)

Utilizator Juve45UAIC Alexandru Ionita Juve45 Data 3 martie 2015 16:53:02
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <bits/stdc++.h>

#define pb push_back
#define DMAX 6000

using namespace std;

int n, m2;
bool p[DMAX], m[DMAX], use[DMAX];
vector <vector <int> > sol;
vector <int>v[DMAX];
vector <int>g[DMAX];

void reset()
{
    for(int i=1;i<=n;i++)
        p[i]=m[i]=0;
}

void dfs_plus(int k)
{
    for(int i=0;i<v[k].size();i++)
    {
        if(p[v[k][i]]==0)
            p[v[k][i]]=1,
            dfs_plus(v[k][i]);
    }
}

void dfs_minus(int k)
{
    for(int i=0;i<g[k].size();i++)
    {
        if(m[g[k][i]]==0)
            m[g[k][i]]=1,
            dfs_minus(g[k][i]);
    }
}

void conex()
{
    vector <int> s;
    for(int i=1;i<=n;i++)
        if(p[i]==m[i] && m[i]==1)
    {
s.pb(i);
use[i]=1;
    }
    if(s.size()>0)
        sol.pb(s);
}

int main()
{
    freopen("ctc.in", "r", stdin);
    freopen("ctc.out", "w", stdout);
    cin>>n>>m2;
    int a, b;
    for(int i=1;i<=m2;i++)
    {
        cin>>a>>b;
        v[a].pb(b);
        g[b].pb(a);
    }

    for(int i=1;i<=n;i++)
        if(!use[i])
        {
        reset();
        dfs_plus(i);
        dfs_minus(i);
        conex();
        }

    cout<<sol.size()<<'\n';

    for(int i=0;i<sol.size();++i)
        for(int j=0;j<sol[i].size();++j)
            cout<<sol[i][j]<<" \n"[j==sol[i].size()-1];


    return 0;


}