Cod sursa(job #802800)

Utilizator zeeboBuzatu Vlad zeebo Data 26 octombrie 2012 20:22:44
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <fstream>
#include <vector>
#define pb push_back
using namespace std;

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

int n,m,nr,v[100001];
bool sel[100001];
vector <int> g[100001],gt[100001],val;
vector < vector<int> > vec;

void read()
{
    int x,y,i;
    f>>n>>m;
    for (i=1;i<=m;i++)
    {
        f>>x>>y;
        g[x].pb(y);
        gt[y].pb(x);
    }
}
void DFplus (int x)
{
    vector <int> :: iterator it;

    sel[x]=true;
    for (it=g[x].begin();it!=g[x].end();it++)
    {
        if (!sel[*it])
        {
            DFplus(*it);
        }
    }
v[++nr]=x;
}
void DFminus (int x)
{
    vector <int> :: iterator it;

    sel[x]=false;val.pb(x);
    for (it=gt[x].begin();it!=gt[x].end();it++)
    {
        if (sel[*it])
        {
            DFminus(*it);
        }
    }
}
void solve ()
{

    for (int i=1;i<=n;i++)
          if (!sel[i]) DFplus(i);

    while (nr)
      {
          if (sel[v[nr]])
          {
              val.clear();
              DFminus(v[nr]);
              vec.pb(val);
          }
          nr--;
      }

}
int main()
{
   vector < vector<int> > :: iterator it;
   vector <int> :: iterator it1;
   read();
   solve();
h<<vec.size()<<'\n';
 for (it=vec.begin();it!=vec.end();it++)
 {
    for (it1=it->begin();it1!=it->end();it1++)
      h<<*it1<<' ';
  h<<'\n';
 }
return 0;
}