Cod sursa(job #1328553)

Utilizator andreiulianAndrei andreiulian Data 28 ianuarie 2015 15:28:55
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.58 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
int N,M,u;
vector<int> s[100005],p[100005],sol[100005];
queue<int> q;
bool viz[100005];
int pp[100005],mm[100005];
void latime_plus(int i);
void latime_minus(int i);
int main()
{
    in>>N>>M;
    int i,j,a,b;
    for(i=1;i<=N;++i) s[i].push_back(0),p[i].push_back(0);
    for(i=1;i<=M;++i)
    {
        in>>a>>b;
        s[a].push_back(b);
        s[a][0]++;
        p[b].push_back(a);
        p[b][0]++;
    }
    for(i=1;i<=N;++i)
    {
        if(!viz[i])
        {
            ++u;
            sol[u].push_back(0);
            latime_plus(i);
            latime_minus(i);
        }
    }
    out<<u<<'\n';
    for(i=1;i<=u;++i)
    {
        for(j=1;j<=sol[i][0];++j)
            out<<sol[i][j]<<' ';
        out<<'\n';
    }
}
void latime_plus(int i)
{
    q.push(i);
    pp[i]=i;
    int j,c;
    while(!q.empty())
    {
        c=q.front();
        q.pop();
        for(j=1;j<=s[c][0];++j)
        {
            if(pp[s[c][j]]!=i)
            {
                pp[s[c][j]]=i;
                q.push(s[c][j]);
            }
        }
    }

}
void latime_minus(int i)
{
    q.push(i);
    mm[i]=i;
    if(pp[i]==i)
        sol[u].push_back(i),sol[u][0]++;
    int j,c;
    while(!q.empty())
    {
        c=q.front();
        q.pop();
        for(j=1;j<=p[c][0];++j)
        {
            if(mm[p[c][j]]!=i)
            {mm[p[c][j]]=i;
            if(pp[p[c][j]]==i) sol[u].push_back(p[c][j]),sol[u][0]++,viz[p[c][j]]=1;
            q.push(p[c][j]);}
        }
    }
}