Pagini recente » Cod sursa (job #2698692) | Cod sursa (job #3148150) | Cod sursa (job #2191969) | Cod sursa (job #519146) | Cod sursa (job #2328173)
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
const int MAX= 100003;
vector <int> gr[MAX], comp[MAX];
stack <int> s, afis;
bool viz[MAX];
int n, m, id[MAX], low[MAX], nc, urm;
ifstream in("ctc.in");
ofstream out("ctc.out");
void tarjan(int nod){
id[nod] = low[nod] = ++urm;
s.push(nod);
viz[nod] = true;
for(unsigned i=0; i<gr[nod].size(); i++)
if(id[gr[nod][i]]==0){
tarjan(gr[nod][i]);
low[nod] = min(low[nod], low[gr[nod][i]]);
}
else
if(viz[gr[nod][i]]==true)
low[nod] = min(low[nod], low[gr[nod][i]]);
if(id[nod] == low[nod]){
nc++;
int v;
do{
v = s.top();
s.pop(); viz[v] = false;
afis.push(v);
}while(v!=nod);
}
}
int main()
{
int i, u, v;
in>>n>>m;
for(i=1; i<=m; i++){
in>>u>>v;
gr[u].push_back(v);
}
for(i=1; i<=n; i++)
if(id[i]==0)
tarjan(i);
out<<nc;
while(!afis.empty()){
int v = afis.top();
afis.pop();
if(id[v] == low[v]) out<<'\n';
out<<v<<' ';
}
return 0;
}