Mai intai trebuie sa te autentifici.
Cod sursa(job #951912)
Utilizator | Data | 22 mai 2013 11:44:12 | |
---|---|---|---|
Problema | Componente tare conexe | Scor | 60 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 2.13 kb |
#include <iostream>
#include<vector>
#include<stack>
#include<fstream>
#define lim 100001
using namespace std;
class tconex {
int n,m,sel[lim];
vector<int> graf[lim],graf_tr[lim],comp;
vector< vector<int> > sol;
stack<int> stiva;
fstream in,out;
public:
tconex(string fin, string fout)
{
in.open(fin.c_str(), ios::in);
out.open(fout.c_str(), ios::out);
}
~tconex()
{
in.close();
out.close();
}
void read()
{
int a,b;
in>>n>>m;
for(int i=1;i<=m;i++)
{
in>>a>>b;
graf[a].push_back(b);
graf_tr[b].push_back(a);
}
for(int i=1;i<=n;i++)
{
sel[i]=0;
}
}
void dfs1(int nod)
{
sel[nod]=1;
vector<int>::iterator it;
for(it=graf[nod].begin();it<graf[nod].end();it++)
{
if(sel[*it]==0)
{
dfs1(*it);
}
}
stiva.push(nod);
}
void dfs2(int nod)
{
sel[nod]=-1;
vector<int>::iterator it;
for(it=graf_tr[nod].begin();it<graf_tr[nod].end();it++)
{
if(sel[*it]!=-1)
dfs2(*it);
}
comp.push_back(nod);
}
void solve()
{
for(int i=1;i<=n;i++)
{
if(sel[i]==0)
{
dfs1(i);
}
}
int aux;
while(!stiva.empty())
{
aux=stiva.top();
stiva.pop();
if(sel[aux]!=-1)
{
dfs2(aux);
sol.push_back(comp);
comp.clear();
}
}
out<<sol.size()<<endl;
vector<int>::iterator it;
for(int i=0;i<sol.size();i++)
{
for(it=sol[i].begin();it<sol[i].end();it++)
{
out<<*it<<" ";
}
out<<endl;
}
}
};
int main()
{
tconex X("ctc.in","ctc.out");
X.read();
X.solve();
return 0;
}