Pagini recente » Cod sursa (job #1217181) | Cod sursa (job #1458304) | Cod sursa (job #2207590) | Cod sursa (job #1729559) | Cod sursa (job #3332532)
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <string>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int n, m, loc, idx[25001], low[25001], nr_comp;
bool inStiva[25001]={false};
vector<int>v[25001];
stack<int>sta;
vector<int>lot[25001];
int timp;
void Tarjan(int nod){
int i, e, s, cont=0;
idx[nod]=low[nod]=++timp;
sta.push(nod);
inStiva[nod]=true;
for(const auto vecin: v[nod]){
if(idx[vecin]==0){
Tarjan(vecin);
low[nod]=min(low[nod], low[vecin]);
}
else{
if(idx[vecin]!=0 && inStiva[vecin]==true){
low[nod]=min(low[nod], idx[vecin]);
}
}
}
if(low[nod]==idx[nod]){
nr_comp++;
loc=-1;
while(loc!=nod){
loc=sta.top();
sta.pop();
inStiva[loc]=false;
lot[nr_comp].push_back(loc);
}
}
}
int main(){
int i, e, s, cont=0, a, b;
f >> n >> m;
for(i=1; i<=m; ++i)
{
f >> a >> b;
v[a].push_back(b);
}
for(i=1; i<=n; ++i)
{
if(idx[i]==0){
Tarjan(i);
}
}
g << nr_comp << "\n";
for(i=1; i<=nr_comp; ++i, g << "\n"){
sort(lot[nr_comp].begin(), lot[nr_comp].end());
for(const auto vecin:lot[i])
g << vecin << " ";
}
return 0;
}