Pagini recente » Istoria paginii runda/minune1/clasament | Cod sursa (job #2391256) | Cod sursa (job #6048) | Cod sursa (job #2012654) | Cod sursa (job #1607551)
#include <fstream>
#include <stack>
#include <vector>
#include <cstring>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int n, m, i, j, nr, niv[100010], low[100010], viz[100010], t, aux, x, y;
vector<int> l[100010], c[100010];
stack<int> st;
void dfs(int x){
t++;
niv[x]=low[x]=t;
st.push(x);
viz[x]=1;
for(int i=0; i<l[x].size(); i++)
{
if(viz[ l[x][i] ]==0){
dfs(l[x][i]);
low[x]=min(low[x], low[ l[x][i] ]);
}
else
low[x]=min(low[x], niv[ l[x][i] ]);
}
if(niv[x]==low[x]&&viz[x]==1)
{
nr++;
do
{
aux=st.top();
niv[aux]=(1<<30);
c[nr].push_back(aux);
st.pop();
}while(x!=aux);
}
}
int main(){
f>>n>>m;
for(i=1; i<=m; i++)
{
f>>x>>y;
l[x].push_back(y);
}
for(i=1; i<=n; i++)
if(niv[i]==0)
dfs(i);
g<<nr<<"\n";
for(i=1; i<=nr; i++)
{
for(j=0; j<c[i].size(); j++)
g<<c[i][j]<<' ';
g<<"\n";
}
return 0;
}