Pagini recente » Cod sursa (job #1070795) | Cod sursa (job #791399) | Cod sursa (job #980071) | Cod sursa (job #893932) | Cod sursa (job #2907428)
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <stack>
#include <algorithm>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
#define MAX 100001
int N,M,x,y,i,idx=1;
vector <int> A[MAX], aux;
int viz[MAX], lowlink[MAX], in_stack[MAX];
stack<int> current_component;
vector<vector <int>> components;
void citire()
{
f >> N >> M;
for (i = 1; i <= M; i++)
{
f >> x >> y;
A[x].push_back(y);
}
f.close();
}
void tarjan(int nod)
{
viz[nod] = lowlink[nod] = idx++;
current_component.push(nod);
in_stack[nod] = 1;
for (int j: A[nod]) {
if (!viz[j]) {
tarjan(j);
lowlink[nod] = min(lowlink[nod], lowlink[j]);
}
else if (in_stack[j])
lowlink[nod]= min(lowlink[nod], viz[j]);
}
if (viz[nod] == lowlink[nod]) {
aux.clear();
int node;
do {
node = current_component.top();
current_component.pop();
aux.push_back(node);
in_stack[node] = 0;
} while (node != nod);
components.push_back(aux);
}
}
int main()
{
// folosesc liste de vecini pentru retinerea grafului
citire();
// marchez toate nodurile ca fiind nevizitate
memset(viz, 0, sizeof(viz));
memset(in_stack, 0, sizeof(in_stack));
for (i=1; i<=N; i++)
if (!viz[i]) {
tarjan(i);
}
g<<components.size()<<endl;
reverse(components.begin(), components.end());
for (i=0; i<components.size(); i++) {
reverse(components[i].begin(), components[i].end());
for (auto j: components[i])
g<<j<<" ";
g<<endl;
}
g.close();
return 0;
}