Cod sursa(job #652279)

Utilizator mihai995mihai995 mihai995 Data 23 decembrie 2011 19:03:37
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.93 kb
#include <fstream>
#include <vector>
using namespace std;

const int N=100005;
int a[N],b[N],stack[N],n;
bool use[N];
vector<int> a1[N],a2[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);
}
*/
void dfs(int x,vector<int> a[],int rez[],int val)
{
    rez[x]=val;
    for (vector<int>::iterator i=a[x].begin();i!=a[x].end();i++)
        if (!rez[*i])
            dfs(*i,a,rez,val);
}

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

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

int main()
{
    int nr=0,x,y,val=0,m;
    in>>n>>m;
    while (m--)
    {
        in>>x>>y;
        a1[x].push_back(y);
        a2[y].push_back(x);
    }
    for (int i=1;i<=n;i++)
        if (!a[i])
            dfs(i,++val);
    val=0;
    for (int i=stack[0];i;i--)
        if (!b[stack[i]])
            df(stack[i],++val);
    for (int i=1;i<=n;i++)
    {
        if (use[i])
            continue;
        rez[++nr].push_back(i);
        for (int j=i+1;j<=n;j++)
            if (a[i]==a[j] && b[i]==b[j])
            {
                use[j]=true;
                rez[nr].push_back(j);
            }
    }
    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;
}