Faits: A. A._, ressortissante portugaise née le *** 1969, est entrée en Suisse le 8 janvier 2009 pour y travailler en tant que barmaid à plein temps. A cette fin, elle a obtenu une autorisation de séjour CE/AELE valable cinq ans, soit du 1er mars 2009 au 28 février 2014. A._ a exercé cette activité à 100% du 1er au 31 mars, puis a conclu, avec la même société, un contrat pour une activité à 50% dès le 1er avril 2009. Elle a été licenciée pour restructuration le 28 février 2010. L'intéressée a alors perçu des indemnités de l'assurance-chômage du 1er mars 2010 au 31 mars 2011; puis, son droit à ces indemnités étant épuisé, elle a bénéficié des prestations de l'aide sociale dès le 1er avril 2011. Par la suite, A._ a occupé un emploi temporaire d'insertion, fourni par un office régional de placement, en qualité d'opératrice auprès de l'administration du 18 octobre 2010 au 17 avril 2011; elle a alors été en arrêt de travail pour cause de maladie du 18 au 21 novembre 2010, du 13 au 24 janvier 2011, du 7 au 8 février et du 15 au 28 février 2011. Dans le cadre du programme d'insertion en qualité de bénéficiaire de l'aide sociale, A._ s'est encore vu attribuer une activité du 1er octobre au 31 décembre 2011 dans l'intendance de B._; son salaire brut mensuel s'élevait à 2'700 fr.; elle a quitté cet emploi le 5 décembre 2011. Par lettre du 8 mai 2012, le Service de la population du canton de Vaud (ci-après: le Service de la population) a informé A._ de son intention de révoquer l'autorisation de séjour de l'intéressée, compte tenu du fait que celle-ci ne pouvait plus se prévaloir de la qualité de travailleur communautaire. Le 24 mai 2012, l'Office régional de placement a clôturé le dossier de l'intéressée. A la même date, A._ a été engagée à 80% auprès de la société C._ SA dans le cadre d'un contrat de mission de trois mois, soit du 24 mai au 24 août 2012. Elle a été en incapacité de travail totale du 8 au 22 juin 2012 et du 26 juin au 10 juillet 2012, puis en incapacité partielle (50%) du 11 au 23 juillet 2012 pour se retrouver à nouveau en incapacité totale du 24 juillet au 7 août 2012. Le 17 septembre 2012, le Service de la population a révoqué l'autorisation de séjour CE/AELE de A._, et a prononcé son renvoi de Suisse dans un délai de trois mois. Il a retenu que le faible nombre d'heures de travail hebdomadaire effectuées par l'intéressée ne lui permettait plus de se prévaloir de la qualité de travailleur communautaire; en outre, celle-ci ne disposait que d'un très faible revenu aléatoire qui n'assurait pas son autonomie financière, si bien qu'elle percevait des prestations de l'aide sociale; elle ne remplissait dès lors pas les conditions lui permettant de séjourner en Suisse sans exercer une activité lucrative. Enfin, sa situation ne constituait pas un cas de rigueur. B. Par arrêt du 21 mars 2013, le Tribunal cantonal du canton de Vaud (ci-après: le Tribunal cantonal) a admis le recours de A._. Il a retenu en substance que l'intimée avait obtenu, à son arrivée en Suisse, une autorisation de séjour CE/AELE (actuellement UE/AELE) avec activité lucrative valable cinq ans; celle-ci avait exercé une première activité lucrative, en qualité de barmaid, du 1er mars 2009 au 28 février 2010. Dès lors que A._ avait effectivement occupé durant un an un emploi qui portait sur une activité économique réelle et effective, il apparaissait qu'elle avait acquis la qualité de travailleuse salariée communautaire au sens de l'art. 6 annexe I de I'Accord du 21 juin 1999 entre la Confédération suisse, d'une part, et la Communauté européenne et ses Etats membres, d'autre part, sur la libre circulation des personnes (ci-après: ALCP ou l'Accord; RS 0.142.112.681). Il en découlait que son titre de séjour en cours de validité ne pouvait lui être retiré du seul fait qu'elle n'occupait plus d'emploi. En effet, toujours selon le Tribunal cantonal, au regard de l'art. 6 par. 6 annexe I ALCP seule une situation de chômage volontaire pouvait justifier la révocation de l'autorisation de séjour CE/AELE de l'intimée; or, le Service de la population ne prétendait pas que A._ était dans une telle situation et aucun élément allant dans ce sens ne ressortait du dossier. Enfin, le fait que l'intéressée soit tombée à la charge de l'assistance publique ne constituait pas un motif de révocation de l'autorisation de séjour CE/AELE au sens de l'art. 5 annexe I ALCP. C. Agissant par la voie du recours en matière de droit public, l'Office fédéral des migrations (ci-après: l'Office fédéral) demande au Tribunal fédéral, sous suite de frais, d'annuler l'arrêt du 21 mars 2013. A._ conclut au rejet du recours. Le Service de la population se rallie aux considérations de l'Office fédéral et demande l'admission du recours. Le Tribunal cantonal se réfère aux considérants de l'arrêt attaqué.