Cod sursa(job #1680687)

Utilizator SlevySlevoaca Stefan-Gabriel Slevy Data 8 aprilie 2016 23:09:22
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.42 kb
#include <iostream>
#include <fstream>
#include <bitset>
#include <vector>
#include <queue>

using namespace std;

ifstream in("ctc.in");
ofstream out("ctc.out");
const int NMAX = 100001;
vector<int> edges[NMAX];
vector<int> edges_t[NMAX];
queue<int> q;
bitset<NMAX> mark;
bitset<NMAX> m_plus;
bitset<NMAX> m_minus;
int n,m;
char buff[NMAX];
int pos = 0;

void Read(int &a)
{
    while(!isdigit(buff[pos]))
        if(++pos == NMAX)
            in.read(buff,NMAX),pos = 0;
    a = 0;
    while(isdigit(buff[pos]))
    {
        a = a*10 + buff[pos]-'0';
        if(++pos == NMAX)
            in.read(buff,NMAX),pos = 0;
    }
}

void read_data()
{
    Read(n);
    Read(m);
    int x,y;
    for(int i=1;i<=m;i++)
    {
        Read(x);
        Read(y);
        edges[x].push_back(y);
        edges_t[y].push_back(x);
    }
    in.close();
}

void bfs_p(int x)
{
    m_plus.set(x);
    q.push(x);
    int y;
    while(!q.empty())
    {
        y = q.front();
        for(unsigned int i=0;i<edges[y].size();i++)
            if(!m_plus.test(edges[y][i]) && !mark.test(edges[y][i]))
            {
                q.push(edges[y][i]);
                m_plus.set(edges[y][i]);
            }
        q.pop();
    }
}


void bfs_m(int x)
{
    m_minus.set(x);
    q.push(x);
    int y;
    if(m_plus.test(x))
    {
        out<<x<<" ";
        mark.set(x);
    }
    while(!q.empty())
    {
        y = q.front();
        for(unsigned int i=0;i<edges_t[y].size();i++)
            if(!m_minus.test(edges_t[y][i]) && !mark.test(edges_t[y][i]))
            {
                q.push(edges_t[y][i]);
                if(m_plus.test(edges_t[y][i]))
                    {
                        mark.set(edges_t[y][i]);
                        out<<edges_t[y][i]<<" ";
                    }
                m_minus.set(edges_t[y][i]);
            }
        q.pop();
    }
}

int main()
{
    read_data();
    int nr = 0;
    out<<"                \n";
    for(int i=1;i<=n;i++)
        if(!edges[i].size() || !edges_t[i].size())
        {
            mark.set(i);
            out<<"\n";
        }
    for(int i=1;i<=n;i++)
        if(!mark.test(i))
    {
        m_plus.reset();
        m_minus.reset();
        bfs_p(i);
        bfs_m(i);
        nr++;
        out<<"\n";
    }
    out.close();
    fstream out("ctc.out");
    out<<nr;
    out.close();
    return 0;
}