Pagini recente » Cod sursa (job #2258401) | Cod sursa (job #3139650) | Cod sursa (job #2256762) | Cod sursa (job #292133) | Cod sursa (job #3235773)
#include <bits/stdc++.h>
using namespace std;
ifstream f ("ctc.in");
ofstream g ("ctc.out");
const int NMAX = 1e5;
const int MMAX = 2e5;
vector<int> adj[NMAX+1];
int idx[NMAX+1], linked[NMAX+1];
bool marked[NMAX+1];
stack<int> stiva;
int cnt;
vector<vector<int>> rez;
void tarjan(int nod){
cnt ++;
linked[nod] = cnt;
idx[nod] = cnt;
stiva.push(nod);
marked[nod] = true;
for(int next : adj[nod]){
if(idx[next] == -1){
tarjan(next);
linked[nod] = min(linked[nod], linked[next]);
}else if(marked[next]){
linked[nod] = min(linked[nod], linked[next]);
}
}
//cout << stiva.size() << endl;
if(idx[nod] == linked[nod]){
vector<int> aux;
while(!stiva.empty() and stiva.top() != nod){
aux.push_back(stiva.top());
marked[stiva.top()] = false;
stiva.pop();
}
aux.push_back(nod);
rez.push_back(aux);
stiva.pop();
}
}
int main()
{
int n, m;
f >> n >> m;
for(int i=1; i<=m; i++){
int x, y;
f >> x >> y;
adj[x].push_back(y);
}
for(int i=1; i<=n; i++)
idx[i] = -1;
for(int i=1; i<=n; i++)
if(idx[i] == -1)
tarjan(i);
g << rez.size() << "\n";
for(int i=0; i<rez.size(); i++){
for(int j=0; j<rez[i].size(); j++)
g << rez[i][j] << ' ';
g << "\n";
}
return 0;
}