Pagini recente » Cod sursa (job #377211) | Cod sursa (job #2371930) | Cod sursa (job #2390806) | Cod sursa (job #1181968) | Cod sursa (job #2052033)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
class graf
{
public:
vector<vector<int> > vecini;
graf(int n = 0)
{
this->n = n;
vecini.resize(n + 1);
viz.resize(n + 1);
}
void AddEdge(int x, int y)
{
vecini[x].push_back(y);
}
void GetStrongComp(vector<vector<int> > &ret)
{
for(int i = 1; i <= n; ++i)
viz[i] = false;
for(int i = 1; i <= n; ++i)
if(viz[i] == false)
DFS(i);
graf tr; //graful transpus
GetTranspose(tr);
for(int i = 1; i <= n; ++i)
viz[i] = false;
while(st.empty() == false)
{
int p = st.top();
st.pop();
if(!viz[p])
{
vector<int> comp;
GetArb(comp, tr, p);
ret.push_back(comp);
}
}
}
private:
void DFS(int current)
{
viz[current] = true;
for(auto v:vecini[current])
if(!viz[v])
DFS(v);
st.push(current);
}
void GetTranspose(graf &ret)
{
ret = graf(n);
for(int i = 1; i <= n; ++i)
for(auto v:vecini[i])
ret.AddEdge(v, i);
}
void GetArb(vector<int> &ret, const graf &gr, int current)
{
viz[current] = true;
ret.push_back(current);
for(auto v:gr.vecini[current])
if(!viz[v])
GetArb(ret, gr, v);
}
int n;
vector<bool> viz;
stack<int> st;
};
int main()
{
ifstream in("ctc.in");
ofstream out("ctc.out");
int n, m;
in >> n >> m;
graf gr(n);
int x, y;
while(m--)
{
in >> x >> y;
gr.AddEdge(x, y);
}
vector<vector<int> > rasp;
gr.GetStrongComp(rasp);
out << rasp.size() << "\n";
for(auto &v:rasp)
{
for(auto nod:v)
out << nod << " ";
out << "\n";
}
in.close();
out.close();
return 0;
}