Cod sursa(job #2344304)

Utilizator Stefan_PiscuPiscu Stefan Constantin Stefan_Piscu Data 14 februarie 2019 22:28:48
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.79 kb
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

struct nod{    int canBeReached, canReach;
               vector<int> toNodes;
               vector<int> fromNodes;
               bool used;
          }p[100003];

int n, m;
vector< vector<int> > Sol;

void MarkNodesPlus(int x=1, int Marker=1)
{
    if(p[x].canBeReached!=Marker)
    {
        p[x].canBeReached=Marker;
        for(int i=0;i<p[x].toNodes.size();++i)
            MarkNodesPlus(p[x].toNodes[i], Marker);
    }

}

void MarkNodesMinus(int x=1, int Marker=1)
{
    if(p[x].canReach!=Marker)
    {
        p[x].canReach=Marker;
        for(int i=0;i<p[x].fromNodes.size();++i)
            MarkNodesMinus(p[x].fromNodes[i], Marker);
    }
}

void add(vector<int> &vec, int x, int t)
{
    if(p[x].canReach==t&&p[x].canBeReached==t&&!p[x].used)
    {
        vec.push_back(x);
        p[x].used=1;
        for(int i=0;i<p[x].toNodes.size();++i)
            add(vec, p[x].toNodes[i], t);
    }
}

vector<int> findStrongConexComponent(int x)
{
    vector<int> StrongConexComponent;
    StrongConexComponent.clear();
    MarkNodesPlus(x, x);
    MarkNodesMinus(x, x);
    add(StrongConexComponent, x, x);
    return StrongConexComponent;
}

int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;++i)
    {
        int x, y;
        fin>>x>>y;
        p[x].toNodes.push_back(y);
        p[y].fromNodes.push_back(x);
    }
    for(int i=1;i<=n;++i)
    {
        if(!p[i].used) Sol.push_back(findStrongConexComponent(i));
    }
    fout<<Sol.size()<<"\n";
    for(int i=0;i<Sol.size();++i)
    {
        for(int j=0;j<Sol[i].size();++j)
            fout<<Sol[i][j]<<" ";
        fout<<"\n";
    }
    return 0;
}