Cod sursa(job #1897755)

Utilizator Cudrici_CarinaCudrici Carina Cudrici_Carina Data 1 martie 2017 17:54:20
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

ifstream fi("ctc.in");
ofstream fo("ctc.out");

const int Inf = 0x3f3f3f3f;
int n, m, a, b;
int idx;
vector<vector<int> > G, sol;
vector<int> index, L, c;
vector<bool> inStack;
stack<int> st;


void Read()
{
    int x,y;
    fi >> n >> m;

    G.resize(n + 1);
    index.resize(n + 1,Inf);
    L.resize(n + 1);
    inStack.resize(n + 1);

    for ( int i = 1; i <= m; ++i )
    {
        fi >> x >> y;
        G[x].push_back(y);
    }

}
void Write()
{
fo << sol.size() << "\n";
for ( size_t i = 0; i < sol.size(); ++i,fo<<'\n' )
    for ( size_t j = 0; j < sol[i].size(); ++j )
            fo << sol[i][j] << " ";
}
void Tarjan(int x)
{

index[x] = L[x] = idx++;
st.push(x);
inStack[x] = true;

for ( const int & y : G[x] )
if ( index[y] == Inf ) // muchie de arbore
           { Tarjan(y);
             L[x] = min(L[x], L[y]);
           }
        else  if( inStack[y] )   //muchie de intoarcere
                 L[x] = min(L[x], index[y]);

if ( index[x] == L[x] )  // am gasit o noua comp.tare conexa
    {
        c.clear();
        int y;
        do
        {   y=st.top();
            st.pop();
            inStack[y] = false;
            c.push_back(y);

        } while ( y != x );
       sol.push_back(c);
    }
}


int main()
{
Read();
for ( int i = 1; i <= n; ++i )
      if ( index[i] == Inf ) Tarjan(i);
Write();


    return 0;
}