Pagini recente » Cod sursa (job #2848219) | Cod sursa (job #1845407) | Cod sursa (job #177013) | Cod sursa (job #896140) | Cod sursa (job #841065)
Cod sursa(job #841065)
#include <fstream>
#include <vector>
#include <stack>
#include <cstdio>
using namespace std;
vector <int> V[100005],Con[100005];
stack <int> ST;
int nrc,t;
int vizitat[100005], is_stack[100005];
int low[100005], high[100005];
ifstream f("ctc.in");
ofstream g("ctc.out");
void pp(int nod){
int k;
do{
k = ST.top();
ST.pop();
Con[nrc].push_back(k);
is_stack[k] = 0;
} while(k!=nod);
nrc++;
}
void tarjan(int nod){
vizitat[nod] = 1;
is_stack[nod] = 1;
low[nod] = high[nod] = t;
ST.push(nod);
t++;
for(vector<int>::iterator it = V[nod].begin();it!=V[nod].end();it++){
if(!vizitat[*it]){
tarjan(*it);
low[nod] = min(low[nod],low[*it]);
}
else if(is_stack[*it])
low[nod] = min(low[nod],high[*it]);
}
if(low[nod] == high[nod])
pp(nod);
}
int main(){
int n,m,x,y;
f >> n >> m;
for(int i=1;i<=m;i++){
f >> x >> y;
V[x].push_back(y);
}
for(int i=1;i<=n;i++)
if(!vizitat[i])
tarjan(i);
g << nrc << '\n';
for(int i=0;i<nrc;i++){
for(vector<int>::iterator j = Con[i].begin();j!=Con[i].end();j++)
g << *j << " ";
g << '\n';
}
f.close();
g.close();
return 0;
}