Pagini recente » Cod sursa (job #2689914) | Cod sursa (job #771041) | Cod sursa (job #3195619) | Cod sursa (job #2406091) | Cod sursa (job #998927)
Cod sursa(job #998927)
#include <fstream>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int MAXN = 100005;
int indxx, n, m, x, y;
struct graph {
vector <int> vecini;
int index;
int lowlink;
bool in_stack;
}nodes[MAXN];
stack <int> stiva;
vector <vector <int> > multimea_componentelor;
vector <int> componenta;
void read() {
fin >> n >> m;
for (int i = 0; i < m; ++i) {
fin >> x >> y;
nodes[x].vecini.push_back(y);
}
}
void tarjan(int nod) {
nodes[nod].index = nodes[nod].lowlink = indxx++;//notam la ce index suntem
stiva.push(nod); nodes[nod].in_stack = true;//bagam in stiva nodul
vector <int>::iterator it;
for (it = nodes[nod].vecini.begin(); it != nodes[nod].vecini.end(); ++it) {
if (nodes[*it].index == -1) {//nod nevizitat
tarjan(*it);
nodes[nod].lowlink = min(nodes[nod].lowlink, nodes[*it].lowlink);
}else if (nodes[*it].in_stack)//daca am mai vizitat nodul, verificam daca acesta se afla inca in stiva
nodes[nod].lowlink = min(nodes[nod].lowlink, nodes[*it].lowlink);
}
if (nodes[nod].index == nodes[nod].lowlink) {//daca nodul node este radacina
componenta.clear();
int naux;
do {
naux = stiva.top();
stiva.pop();
componenta.push_back(naux);
nodes[naux].in_stack = false;//am scos din stiva nodul naux
}while (nod != naux);
multimea_componentelor.push_back(componenta);
}
}
void write() {
fout << multimea_componentelor.size() << '\n';
for (unsigned int i = 0; i < multimea_componentelor.size(); ++i) {
for (unsigned int j = 0; j < multimea_componentelor[i].size(); ++j)
fout << multimea_componentelor[i][j] << ' ';
fout << '\n';
}
}
int main() {
read();
for (int i = 1; i <= n; ++i)
nodes[i].index = -1;
for (int i = 1; i <= n; ++i)
if (nodes[i].index == -1)//daca nodul i nu a mai fost vizitat, apelam tarjan()
tarjan(i);
write();
fin.close();
fout.close();
return 0;
}