Cod sursa(job #1525354)

Utilizator andrew_assassin789Andrei Manea andrew_assassin789 Data 14 noiembrie 2015 23:42:10
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.72 kb
#include <fstream>
#include <vector>
#include <queue>
#define w 5000
using namespace std;
struct con {int v;bool sens;};
vector <con> a[w];
queue <int> q;
vector <int> l[w];
bool up[w],um[w],viz[w];
void bfs(int xx)
{
    int x,i;
    con y;
    q.push(xx);
    while(!q.empty())
    {
        x=q.front();
        q.pop();
        for (i=0;i<=a[x].size()-1;i++)
        {
            y=a[x][i];
            if ((!up[y.v])&&y.sens)
            {
                up[y.v]=1;
                q.push(y.v);
            }
        }
    }
    q.push(xx);
    while(!q.empty())
    {
        x=q.front();
        q.pop();
        for (i=0;i<=a[x].size()-1;i++)
        {
            y=a[x][i];
            if ((!um[y.v])&&(!y.sens))
            {
                um[y.v]=1;
                q.push(y.v);
            }
        }
    }
}
int main()
{
    ifstream f("ctc.in");
    ofstream g("ctc.out");
    int n,m,i,j,x,y,nr=0;
    f>>n>>m;
    con r;
    for (i=1;i<=m;i++)
    {
        f>>x>>y;
        r.v=y;r.sens=1;
        a[x].push_back(r);
        r.v=x;r.sens=0;
        a[y].push_back(r);
    }
    for (x=1;x<=n;x++)
    {
        if (!viz[x])
        {
            nr++;
            up[x]=1;um[x]=1;
            bfs(x);
            for (i=1;i<=n;i++)
            {
                if (up[i]&&um[i])
                {
                    viz[i]=1;
                    l[nr].push_back(i);
                }
                up[i]=um[i]=0;
            }
        }
    }
    g<<nr<<'\n';
    for (i=1;i<=nr;i++)
    {
        for (j=0;j<=l[i].size()-1;j++)
        {
            g<<l[i][j]<<' ';
        }
        g<<'\n';
    }
    f.close();
    g.close();
    return 0;
}