Pagini recente » Cod sursa (job #2124078) | Cod sursa (job #1151527) | Cod sursa (job #2159537) | Cod sursa (job #1380619) | Cod sursa (job #2797123)
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <stack>
#define VALMAX 100005
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector<int> componente[VALMAX+1];
stack <int> Stiva;
int vizitat[VALMAX + 1];
int vizitatT[VALMAX + 1];
struct nod{
nod *next;
int val;
};
class OrientedGraph{
protected:
nod *varfuri[VALMAX];
nod *varfuriT[VALMAX];
int nrVarfuri;
int nrMuchii;
int varfStart;
public:
OrientedGraph(){
vizitAll();
//makeDrc0();
}
OrientedGraph(int nrV, int nrM): nrVarfuri(nrV), nrMuchii(nrM){
vizitAll();
//makeDrc0();
}
void vizitAll(){
/*
for(int i = 1;i<=VALMAX;++i){
vizitat[i] = 0;
vizitatT[i] = 0;
}
*/
}
void citireOrientat(){
if(!nrVarfuri)fin>>nrVarfuri>>nrMuchii;
/// default behavior
for(int i = 1;i<=nrMuchii;++i){
int x, y;
fin>>x>>y;
nod *p = new nod;
p->val = y;
p->next = varfuri[x];
varfuri[x] = p;
p = new nod;
p->val = x;
p->next = varfuriT[y];
varfuriT[y] = p;
}
}
void afisare(){
for(int i = 1;i<=nrVarfuri;++i){
nod *p = varfuri[i];
cout<<"varf: "<<i<<"...: ";
while(p){
cout<<p->val<<" ";
p = p->next;
}
cout<<endl;
}
}
};
class ComponenteTareConexe: public OrientedGraph{
public:
ComponenteTareConexe(): OrientedGraph(){}
ComponenteTareConexe(int nrV, int nrM): OrientedGraph(nrV, nrM){}
void dfs1(int varf){
vizitat[varf] = 1;
nod *p = varfuri[varf];
while(p){
if(!vizitat[p->val]){
dfs1(p->val);
}
p = p->next;
}
Stiva.push(varf);
}
void dfs2(int varf, int contorComp){
vizitatT[varf] = 1;
nod *p = varfuriT[varf];
componente[contorComp].push_back(varf);
while(p){
if(!vizitatT[p->val]){
dfs2(p->val, contorComp);
}
p = p->next;
}
}
void parcurgere(){
for(int i = 1;i<=nrVarfuri;++i){
if(!vizitat[i]){
dfs1(i);
}
}
}
void componenteTare(){
int contorComp = 0;
while(!Stiva.empty()){
int varf = Stiva.top();
Stiva.pop(); /// nu l mai folosim
if(!vizitatT[varf]){
contorComp++;
dfs2(varf, contorComp);
}
}
fout<<contorComp<<endl;
for(int i = 1;i<=contorComp;++i){
int lungime = componente[i].size();
for(int j = 0;j<lungime;++j){
fout<<componente[i][j]<<" ";
}
fout<<endl;
}
}
};
int main()
{
ComponenteTareConexe g;
g.citireOrientat();
//g.afisare();
g.parcurgere();
g.componenteTare();
return 0;
}