Pagini recente » Cod sursa (job #3296410) | Cod sursa (job #2758297) | Cod sursa (job #626219) | Cod sursa (job #2936506) | Cod sursa (job #2660703)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <cstring>
#define NMAX 100010
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
typedef struct {
int index;
int lowlink;
bool onStack;
} nod;
vector<nod> listaNoduri;
vector<int> listaArce[NMAX];
vector<vector<int>> listaComponente;
stack<int> S;
int n, m;
int ix = 0;
int k = 0;
void strongconnect(int v)
{
listaNoduri[v].index = ix;
listaNoduri[v].lowlink = ix;
ix++;
S.push(v);
listaNoduri[v].onStack = true;
for (int i = 0; i < listaArce[v].size(); i++)
{
int w = listaArce[v][i];
if (listaNoduri[w].index == -1)
{
strongconnect(w);
listaNoduri[v].lowlink = min(listaNoduri[v].lowlink, listaNoduri[w].lowlink);
}
else if (listaNoduri[w].onStack)
listaNoduri[v].lowlink = min(listaNoduri[v].lowlink, listaNoduri[w].index);
}
if (listaNoduri[v].lowlink == listaNoduri[v].index)
{
k++;
vector<int> L;
int w;
do {
w = S.top();
S.pop();
listaNoduri[w].onStack = false;
L.push_back(w);
} while (v != w);
listaComponente.push_back(L);
}
}
// https://www.infoarena.ro/problema/ctc
//
int main()
{
f >> n >> m;
for (unsigned int i = 0; i < m; i++)
{
int nodS, nodD;
f >> nodS >> nodD;
listaArce[nodS].push_back(nodD);
}
for (unsigned int i = 1; i <= n + 1; i++)
listaNoduri.push_back({-1, -1, false});
for (unsigned int i = 1; i <= n; i++)
{
if (listaNoduri[i].index == -1)
strongconnect(i);
}
cout << k << '\n';
for (int i = 0; i < listaComponente.size(); i++)
{
for (int j = 0; j < listaComponente[i].size(); j++)
cout << listaComponente[i][j] << ' ' ;
cout << '\n';
}
return 0;
}