Cod sursa(job #1131896)

Utilizator Catalina_BrinzaBrinza Catalina Catalina_Brinza Data 1 martie 2014 22:43:31
Problema Componente tare conexe Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.61 kb
//
//  main.cpp
//  ctc
//
//  Created by Catalina Brinza on 3/1/14.
//  Copyright (c) 2014 Catalina Brinza. All rights reserved.
//

#include <fstream>
#include <vector>
#include <stack>
#define nr 100030
using namespace std;


ifstream f("ctc.in");
ofstream g("ctc.out");

vector <int> v[nr];
vector <bool> visit, instack;
vector <int> c,ind;
int low[nr];
int k=0;
stack <int> s;
vector <vector<int>> liste;

void tarjan(int i)
{
    low[i]=k;
    ind[i]=k;
    k++;
    s.push(i);
    instack[i]=true;
    for (int j=0;j<v[i].size();++j)
    
        if (ind[v[i][j]]==-1)
        {
            tarjan(v[i][j]);
            if (low[v[i][j]]<low[i]) low [i]=low [v[i][j]];
            }
            else if (instack[v[i][j]] && low[v[i][j]]<low[i]) low [i]=low[v[i][j]];
    
    if (low[i]==ind[i])
    {
        c.clear();
        while (i!=s.top())
        {
            c.push_back(s.top());
             instack[s.top()]=false;
            s.pop(); 
        }
        c.push_back(i);
        instack[i]=false;
        s.pop();
       
        liste.push_back(c);
        
    }
        
        
        return;
    
    
}

int main(int argc, const char * argv[])
{int n,m,i,x,y,j;

    f>>n>>m;
    for (i=0;i<m;++i)
    {
        f>>x>>y;
        v[x].push_back(y);
    }
    for (i=1;i<=n+10;++i)
    {
        visit.push_back(false);
        instack.push_back(false);
        ind.push_back(-1);
    }
    for (i=1;i<=n;++i)
        if (ind[i]==-1) tarjan(i);
    g<<liste.size()<<"\n";
    for (i=0;i<=liste.size();++i)
    {
        for (j=0;j<liste[i].size();++j) g<<liste[i][j]<<' ';
        g<<"\n";
            
    }
    return 0;
}